OpenRaiser/Intern-Atlas huggingface dataset:
Online Ad Slotting With Cancellations
Venue: arXiv cs.GT 2008
Year: 2008

Many advertisers buy advertisements (ads) on the Internet or on traditional media and seek simple, online mechanisms to reserve ad slots in advance. Media publishers represent a vast and varying inventory, and they too seek automatic, online mechanisms for pricing and allocating such reservations. In this paper, we present and study a simple model for auctioning such ad slots in advance. Bidders arrive sequentially and report which slots they are interested in. The seller must decide immediately whether or not to grant a reservation. Our model allows a seller to accept reservations, but possibly cancel the allocations later and pay the bidder a cancellation compensation (bump payment). Our main result is an online mechanism to derive prices and bump payments that is efficient to implement. This mechanism has many desirable properties. It is individually rational; winners have an incentive to be honest and bidding one's true value dominates any lower bid. Our mechanism's efficiency is within a constant fraction of the a posteriori optimally efficient solution. Its revenue is within a constant fraction of the a posteriori revenue of the Vickrey-Clarke-Groves mechanism. Our results make no assumptions about the order of arrival of bids or the value distribution of bidders and still hold if the items for sale are elements of a matroid, a more general setting than slot allocation.
Optimal Node Density for Two-Dimensional Sensor Arrays
Venue: arXiv cs.IT 2008
Year: 2008

The problem of optimal node density for ad hoc sensor networks deployed for making inferences about two dimensional correlated random fields is considered. Using a symmetric first order conditional autoregressive Gauss-Markov random field model, large deviations results are used to characterize the asymptotic per-node information gained from the array. This result then allows an analysis of the node density that maximizes the information under an energy constraint, yielding insights into the trade-offs among the information, density and energy.
Assessment of effective parameters on dilution using approximate reasoning methods in longwall mining method, Iran coal mines
Venue: arXiv cs.AI 2008
Year: 2008

Approximately more than 90% of all coal production in Iranian underground mines is derived directly longwall mining method. Out of seam dilution is one of the essential problems in these mines. Therefore the dilution can impose the additional cost of mining and milling. As a result, recognition of the effective parameters on the dilution has a remarkable role in industry. In this way, this paper has analyzed the influence of 13 parameters (attributed variables) versus the decision attribute (dilution value), so that using two approximate reasoning methods, namely Rough Set Theory (RST) and Self Organizing Neuro- Fuzzy Inference System (SONFIS) the best rules on our collected data sets has been extracted. The other benefit of later methods is to predict new unknown cases. So, the reduced sets (reducts) by RST have been obtained. Therefore the emerged results by utilizing mentioned methods shows that the high sensitive variables are thickness of layer, length of stope, rate of advance, number of miners, type of advancing.
On the Probability Distribution of Superimposed Random Codes
Venue: arXiv cs.DB 2008
Year: 2008

A systematic study of the probability distribution of superimposed random codes is presented through the use of generating functions. Special attention is paid to the cases of either uniformly distributed but not necessarily independent or non uniform but independent bit structures. Recommendations for optimal coding strategies are derived.
Swarm-Based Spatial Sorting
Venue: arXiv cs.AI 2008
Year: 2008

Purpose: To present an algorithm for spatially sorting objects into an annular structure. Design/Methodology/Approach: A swarm-based model that requires only stochastic agent behaviour coupled with a pheromone-inspired "attraction-repulsion" mechanism. Findings: The algorithm consistently generates high-quality annular structures, and is particularly powerful in situations where the initial configuration of objects is similar to those observed in nature. Research limitations/implications: Experimental evidence supports previous theoretical arguments about the nature and mechanism of spatial sorting by insects. Practical implications: The algorithm may find applications in distributed robotics. Originality/value: The model offers a powerful minimal algorithmic framework, and also sheds further light on the nature of attraction-repulsion algorithms and underlying natural processes.
Efficiently Testing Sparse GF(2) Polynomials
Venue: arXiv cs.CC 2008
Year: 2008

We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function $f: \{0,1\}^n \to \{0,1\}$ is an $s$-sparse GF(2) polynomial versus $\eps$-far from every such polynomial. Our algorithm makes $\poly(s,1/\eps)$ black-box queries to $f$ and runs in time $n \cdot \poly(s,1/\eps)$. The only previous algorithm for this testing problem \cite{DLM+:07} used poly$(s,1/\eps)$ queries, but had running time exponential in $s$ and super-polynomial in $1/\eps$. Our approach significantly extends the ``testing by implicit learning'' methodology of \cite{DLM+:07}. The learning component of that earlier work was a brute-force exhaustive search over a concept class to find a hypothesis consistent with a sample of random examples. In this work, the learning component is a sophisticated exact learning algorithm for sparse GF(2) polynomials due to Schapire and Sellie \cite{SchapireSellie:96}. A crucial element of this work, which enables us to simulate the membership queries required by \cite{SchapireSellie:96}, is an analysis establishing new properties of how sparse GF(2) polynomials simplify under certain restrictions of ``low-influence'' sets of variables.
Next Challenges in Bringing Artificial Immune Systems to Production in Network Security
Venue: arXiv cs.MA 2008
Year: 2008

The human immune system protects the human body against various pathogens like e.g. biological viruses and bacteria. Artificial immune systems reuse the architecture, organization, and workflows of the human immune system for various problems in computer science. In the network security, the artificial immune system is used to secure a network and its nodes against intrusions like viruses, worms, and trojans. However, these approaches are far away from production where they are academic proof-of-concept implementations or use only a small part to protect against a certain intrusion. This article discusses the required steps to bring artificial immune systems into production in the network security domain. It furthermore figures out the challenges and provides the description and results of the prototype of an artificial immune system, which is SANA called.
A Network Protection Framework through Artificial Immunity
Venue: arXiv cs.MA 2008
Year: 2008

Current network protection systems use a collection of intelligent components - e.g. classifiers or rule-based firewall systems to detect intrusions and anomalies and to secure a network against viruses, worms, or trojans. However, these network systems rely on individuality and support an architecture with less collaborative work of the protection components. They give less administration support for maintenance, but offer a large number of individual single points of failures - an ideal situation for network attacks to succeed. In this work, we discuss the required features, the performance, and the problems of a distributed protection system called {\it SANA}. It consists of a cooperative architecture, it is motivated by the human immune system, where the components correspond to artificial immune cells that are connected for their collaborative work. SANA promises a better protection against intruders than common known protection systems through an adaptive self-management while keeping the resources efficiently by an intelligent reduction of redundancies. We introduce a library of several novel and common used protection components and evaluate the performance of SANA by a proof-of-concept implementation.
Platform-Independent Firewall Policy Representation
Venue: arXiv cs.CR 2008
Year: 2008

In this paper we will discuss the design of abstract firewall model along with platform-independent policy definition language. We will also discuss the main design challenges and solutions to these challenges, as well as examine several differences in policy semantics between vendors and how it could be mapped to our platform-independent language. We will also touch upon a processing model, describing the mechanism by which an abstract policy could be compiled into a concrete firewall policy syntax. We will discuss briefly some future research directions, such as policy optimization and validation
Rollout Sampling Approximate Policy Iteration
Venue: arXiv cs.LG 2008
Year: 2008

Several researchers have recently investigated the connection between reinforcement learning and classification. We are motivated by proposals of approximate policy iteration schemes without value functions which focus on policy representation using classifiers and address policy learning as a supervised learning problem. This paper proposes variants of an improved policy iteration scheme which addresses the core sampling problem in evaluating a policy through simulation as a multi-armed bandit machine. The resulting algorithm offers comparable performance to the previous algorithm achieved, however, with significantly less computational effort. An order of magnitude improvement is demonstrated experimentally in two standard reinforcement learning domains: inverted pendulum and mountain-car.
Independence of P vs. NP in regards to oracle relativizations
Venue: arXiv cs.CC 2008
Year: 2008

This is the third article in a series of four articles dealing with the P vs. NP question. The purpose of this work is to demonstrate that the methods used in the first two articles of this series are not affected by oracle relativizations. Furthermore, the solution to the P vs. NP problem is actually independent of oracle relativizations.
Computing the fixing group of a rational function
Venue: arXiv cs.SC 2008
Year: 2008

Let G=Aut_K (K(x)) be the Galois group of the transcendental degree one pure field extension K(x)/K. In this paper we describe polynomial time algorithms for computing the field Fix(H) fixed by a subgroup H < G and for computing the fixing group G_f of a rational function f in K(x).
An optimization problem on the sphere
Venue: arXiv cs.LG 2008
Year: 2008

We prove existence and uniqueness of the minimizer for the average geodesic distance to the points of a geodesically convex set on the sphere. This implies a corresponding existence and uniqueness result for an optimal algorithm for halfspace learning, when data and target functions are drawn from the uniform distribution.
A Kernel Method for the Two-Sample Problem
Venue: arXiv cs.LG 2008
Year: 2008

We propose a framework for analyzing and comparing distributions, allowing us to design statistical tests to determine if two samples are drawn from different distributions. Our test statistic is the largest difference in expectations over functions in the unit ball of a reproducing kernel Hilbert space (RKHS). We present two tests based on large deviation bounds for the test statistic, while a third is based on the asymptotic distribution of this statistic. The test statistic can be computed in quadratic time, although efficient linear time approximations are available. Several classical metrics on distributions are recovered when the function space used to compute the difference in expectations is allowed to be more general (eg. a Banach space). We apply our two-sample tests to a variety of problems, including attribute matching for databases using the Hungarian marriage method, where they perform strongly. Excellent performance is also obtained when comparing distributions over graphs, for which these are the first such tests.
Algorithms for Büchi Games
Venue: arXiv cs.GT 2008
Year: 2008

The classical algorithm for solving Büchi games requires time $O(n\cdot m)$ for game graphs with $n$ states and $m$ edges. For game graphs with constant outdegree, the best known algorithm has running time $O(n^2/\log n)$. We present two new algorithms for Büchi games. First, we give an algorithm that performs at most $O(m)$ more work than the classical algorithm, but runs in time O(n) on infinitely many graphs of constant outdegree on which the classical algorithm requires time $O(n^2)$. Second, we give an algorithm with running time $O(n\cdot m\cdot\logδ(n)/\log n)$, where $1\leδ(n)\le n$ is the outdegree of the game graph. Note that this algorithm performs asymptotically better than the classical algorithm if $δ(n)=O(\log n)$.
Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems
Venue: arXiv cs.DS 2008
Year: 2008

We investigate the problem of computing a minimum set of solutions that approximates within a specified accuracy $ε$ the Pareto curve of a multiobjective optimization problem. We show that for a broad class of bi-objective problems (containing many important widely studied problems such as shortest paths, spanning tree, and many others), we can compute in polynomial time an $ε$-Pareto set that contains at most twice as many solutions as the minimum such set. Furthermore we show that the factor of 2 is tight for these problems, i.e., it is NP-hard to do better. We present upper and lower bounds for three or more objectives, as well as for the dual problem of computing a specified number $k$ of solutions which provide a good approximation to the Pareto curve.
MAPEL: Achieving Global Optimality for a Non-convex Wireless Power Control Problem
Venue: arXiv cs.NI 2008
Year: 2008

Achieving weighted throughput maximization (WTM) through power control has been a long standing open problem in interference-limited wireless networks. The complicated coupling between the mutual interferences of links gives rise to a non-convex optimization problem. Previous work has considered the WTM problem in the high signal to interference-and-noise ratio (SINR) regime, where the problem can be approximated and transformed into a convex optimization problem through proper change of variables. In the general SINR regime, however, the approximation and transformation approach does not work. This paper proposes an algorithm, MAPEL, which globally converges to a global optimal solution of the WTM problem in the general SINR regime. The MAPEL algorithm is designed based on three key observations of the WTM problem: (1) the objective function is monotonically increasing in SINR, (2) the objective function can be transformed into a product of exponentiated linear fraction functions, and (3) the feasible set of the equivalent transformed problem is always normal although not necessarily convex. The MAPLE algorithm finds the desired optimal power control solution by constructing a series of polyblocks that approximate the feasible SINR region in increasing precision. Furthermore, by tuning the approximation factor in MAPEL, we could engineer a desirable tradeoff between optimality and convergence time. MAPEL provides an important benchmark for performance evaluation of other heuristic algorithms targeting the same problem. With the help of MAPEL, we evaluate the performance of several respective algorithms through extensive simulations.
Sample Selection Bias Correction Theory
Venue: arXiv cs.LG 2008
Year: 2008

This paper presents a theoretical analysis of sample selection bias correction. The sample bias correction technique commonly used in machine learning consists of reweighting the cost of an error on each training point of a biased sample to more closely reflect the unbiased distribution. This relies on weights derived by various estimation techniques based on finite samples. We analyze the effect of an error in that estimation on the accuracy of the hypothesis returned by the learning algorithm for two estimation techniques: a cluster-based estimation technique and kernel mean matching. We also report the results of sample bias correction experiments with several data sets using these techniques. Our analysis is based on the novel concept of distributional stability which generalizes the existing concept of point-based stability. Much of our work and proof techniques can be used to analyze other importance weighting techniques and their effect on accuracy when using a distributionally stable algorithm.
Compressing Binary Decision Diagrams
Venue: arXiv cs.AI 2008
Year: 2008

The paper introduces a new technique for compressing Binary Decision Diagrams in those cases where random access is not required. Using this technique, compression and decompression can be done in linear time in the size of the BDD and compression will in many cases reduce the size of the BDD to 1-2 bits per node. Empirical results for our compression technique are presented, including comparisons with previously introduced techniques, showing that the new technique dominate on all tested instances.
Design of Attitude Stability System for Prolate Dual-spin Satellite in Its Inclined Elliptical Orbit
Venue: arXiv cs.RO 2008
Year: 2008

In general, most of communication satellites were designed to be operated in geostationary orbit. And many of them were designed in prolate dual-spin configuration. As a prolate dual-spin vehicle, they have to be stabilized against their internal energy dissipation effect. Several countries that located in southern hemisphere, has shown interest to use communication satellite. Because of those countries southern latitude, an idea emerged to incline the communication satellite (due to its prolate dualspin configuration) in elliptical orbit. This work is focused on designing Attitude Stability System for prolate dual-spin satellite in the effect of perturbed field of gravity due to the inclination of its elliptical orbit. DANDE (De-spin Active Nutation Damping Electronics) provides primary stabilization method for the satellite in its orbit. Classical Control Approach is used for the iteration of DANDE parameters. The control performance is evaluated based on time response analysis.
Constructing Folksonomies from User-specified Relations on Flickr
Venue: arXiv cs.AI 2008
Year: 2008

Many social Web sites allow users to publish content and annotate with descriptive metadata. In addition to flat tags, some social Web sites have recently began to allow users to organize their content and metadata hierarchically. The social photosharing site Flickr, for example, allows users to group related photos in sets, and related sets in collections. The social bookmarking site Del.icio.us similarly lets users group related tags into bundles. Although the sites themselves don't impose any constraints on how these hierarchies are used, individuals generally use them to capture relationships between concepts, most commonly the broader/narrower relations. Collective annotation of content with hierarchical relations may lead to an emergent classification system, called a folksonomy. While some researchers have explored using tags as evidence for learning folksonomies, we believe that hierarchical relations described above offer a high-quality source of evidence for this task. We propose a simple approach to aggregate shallow hierarchies created by many distinct Flickr users into a common folksonomy. Our approach uses statistics to determine if a particular relation should be retained or discarded. The relations are then woven together into larger hierarchies. Although we have not carried out a detailed quantitative evaluation of the approach, it looks very promising since it generates very reasonable, non-trivial hierarchies.
An NP-hardness Result on the Monoid Frobenius Problem
Venue: arXiv cs.DM 2008
Year: 2008

The following problem is NP-hard: given a regular expression $E$, decide if $E^*$ is not co-finite.
Design and Implementation Aspects of a novel Java P2P Simulator with GUI
Venue: arXiv cs.NI 2008
Year: 2008

Peer-to-peer networks consist of thousands or millions of nodes that might join and leave arbitrarily. The evaluation of new protocols in real environments is many times practically impossible, especially at design and testing stages. The purpose of this paper is to describe the implementation aspects of a new Java based P2P simulator that has been developed to support scalability in the evaluation of such P2P dynamic environments. Evolving the functionality presented by previous solutions, we provide a friendly graphical user interface through which the high-level theoretic researcher/designer of a P2P system can easily construct an overlay with the desirable number of nodes and evaluate its operations using a number of key distributions. Furthermore, the simulator has built-in ability to produce statistics about the distributed structure. Emphasis was given to the parametrical configuration of the simulator. As a result the developed tool can be utilized in the simulation and evaluation procedures of a variety of different protocols, with only few changes in the Java code.
Succinct Geometric Indexes Supporting Point Location Queries
Venue: arXiv cs.CG 2008
Year: 2008

We propose to design data structures called succinct geometric indexes of negligible space (more precisely, o(n) bits) that, by taking advantage of the n points in the data set permuted and stored elsewhere as a sequence, to support geometric queries in optimal time. Our first and main result is a succinct geometric index that can answer point location queries, a fundamental problem in computational geometry, on planar triangulations in O(lg n) time. We also design three variants of this index. The first supports point location using $\lg n + 2\sqrt{\lg n} + O(\lg^{1/4} n)$ point-line comparisons. The second supports point location in o(lg n) time when the coordinates are integers bounded by U. The last variant can answer point location in O(H+1) expected time, where H is the entropy of the query distribution. These results match the query efficiency of previous point location structures that use O(n) words or O(n lg n) bits, while saving drastic amounts of space. We then generalize our succinct geometric index to planar subdivisions, and design indexes for other types of queries. Finally, we apply our techniques to design the first implicit data structures that support point location in $O(\lg^2 n)$ time.
Neural network learning of optimal Kalman prediction and control
Venue: arXiv cs.NE 2008
Year: 2008

Although there are many neural network (NN) algorithms for prediction and for control, and although methods for optimal estimation (including filtering and prediction) and for optimal control in linear systems were provided by Kalman in 1960 (with nonlinear extensions since then), there has been, to my knowledge, no NN algorithm that learns either Kalman prediction or Kalman control (apart from the special case of stationary control). Here we show how optimal Kalman prediction and control (KPC), as well as system identification, can be learned and executed by a recurrent neural network composed of linear-response nodes, using as input only a stream of noisy measurement data. The requirements of KPC appear to impose significant constraints on the allowed NN circuitry and signal flows. The NN architecture implied by these constraints bears certain resemblances to the local-circuit architecture of mammalian cerebral cortex. We discuss these resemblances, as well as caveats that limit our current ability to draw inferences for biological function. It has been suggested that the local cortical circuit (LCC) architecture may perform core functions (as yet unknown) that underlie sensory, motor,and other cortical processing. It is reasonable to conjecture that such functions may include prediction, the estimation or inference of missing or noisy sensory data, and the goal-driven generation of control signals. The resemblances found between the KPC NN architecture and that of the LCC are consistent with this conjecture.