OpenRaiser/Intern-Atlas huggingface dataset:
Directed Spanners via Flow-Based Linear Programs
Venue: arXiv cs.DS 2010
Year: 2010

We examine directed spanners through flow-based linear programming relaxations. We design an $Õ(n^{2/3})$-approximation algorithm for the directed $k$-spanner problem that works for all $k\geq 1$, which is the first sublinear approximation for arbitrary edge-lengths. Even in the more restricted setting of unit edge-lengths, our algorithm improves over the previous $Õ(n^{1-1/k})$ approximation of Bhattacharyya et al. when $k\ge 4$. For the special case of $k=3$ we design a different algorithm achieving an $Õ(\sqrt{n})$-approximation, improving the previous $Õ(n^{2/3})$. Both of our algorithms easily extend to the fault-tolerant setting, which has recently attracted attention but not from an approximation viewpoint. We also prove a nearly matching integrality gap of $Ω(n^{\frac13 - ε})$ for any constant $ε> 0$. A virtue of all our algorithms is that they are relatively simple. Technically, we introduce a new yet natural flow-based relaxation, and show how to approximately solve it even when its size is not polynomial. The main challenge is to design a rounding scheme that "coordinates" the choices of flow-paths between the many demand pairs while using few edges overall. We achieve this, roughly speaking, by randomization at the level of vertices.
PADDLE: Proximal Algorithm for Dual Dictionaries LEarning
Venue: arXiv cs.LG 2010
Year: 2010

Recently, considerable research efforts have been devoted to the design of methods to learn from data overcomplete dictionaries for sparse coding. However, learned dictionaries require the solution of an optimization problem for coding new data. In order to overcome this drawback, we propose an algorithm aimed at learning both a dictionary and its dual: a linear mapping directly performing the coding. By leveraging on proximal methods, our algorithm jointly minimizes the reconstruction error of the dictionary and the coding error of its dual; the sparsity of the representation is induced by an $\ell_1$-based penalty on its coefficients. The results obtained on synthetic data and real images show that the algorithm is capable of recovering the expected dictionaries. Furthermore, on a benchmark dataset, we show that the image features obtained from the dual matrix yield state-of-the-art classification performance while being much less computational intensive.
Lossy compression of discrete sources via Viterbi algorithm
Venue: arXiv cs.IT 2010
Year: 2010

We present a new lossy compressor for discrete-valued sources. For coding a sequence $x^n$, the encoder starts by assigning a certain cost to each possible reconstruction sequence. It then finds the one that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of each sequence is a linear combination of its distance from the sequence $x^n$ and a linear function of its $k^{\rm th}$ order empirical distribution. The structure of the cost function allows the encoder to employ the Viterbi algorithm to recover the minimizer of the cost. We identify a choice of the coefficients comprising the linear function of the empirical distribution used in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance of any stationary ergodic source in the limit of large $n$, provided that $k$ diverges as $o(\log n)$. Iterative techniques for approximating the coefficients, which alleviate the computational burden of finding the optimal coefficients, are proposed and studied.
Comments on Degrees of freedom region for $K$-user interference channel with $M$ antennas
Venue: arXiv cs.IT 2010
Year: 2010

For a $K$-user interference channel with $M$ antenna at each transmitter and each receiver, the maximum total DoF of this channel has been previously determined to be $\max \sum_{k=1}^K d_k = MK/2$. However, the DoF region remains to be unknown. In this short note, through a simple time-sharing argument, we obtain the degrees of freedom (DoF) region of this channel.
A probabilistic and RIPless theory of compressed sensing
Venue: arXiv cs.IT 2010
Year: 2010

This paper introduces a simple and very general theory of compressive sensing. In this theory, the sensing mechanism simply selects sensing vectors independently at random from a probability distribution F; it includes all models - e.g. Gaussian, frequency measurements - discussed in the literature, but also provides a framework for new measurement strategies as well. We prove that if the probability distribution F obeys a simple incoherence property and an isotropy property, one can faithfully recover approximately sparse signals from a minimal number of noisy measurements. The novelty is that our recovery results do not require the restricted isometry property (RIP) - they make use of a much weaker notion - or a random model for the signal. As an example, the paper shows that a signal with s nonzero entries can be faithfully recovered from about s log n Fourier coefficients that are contaminated with noise.
Interference Alignment Through User Cooperation for Two-cell MIMO Interfering Broadcast Channels
Venue: arXiv cs.IT 2010
Year: 2010

This paper focuses on two-cell multiple-input multiple-output (MIMO) Gaussian interfering broadcast channels (MIMO-IFBC) with $K$ cooperating users on the cell-boundary of each BS. It corresponds to a downlink scenario for cellular networks with two base stations (BSs), and $K$ users equipped with Wi-Fi interfaces enabling to cooperate among users on a peer-to-peer basis. In this scenario, we propose a novel interference alignment (IA) technique exploiting user cooperation. Our proposed algorithm obtains the achievable degrees of freedom (DoF) of 2K when each BS and user have $M=K+1$ transmit antennas and $N=K$ receive antennas, respectively. Furthermore, the algorithm requires only a small amount of channel feedback information with the aid of the user cooperation channels. The simulations demonstrate that not only are the analytical results valid, but the achievable DoF of our proposed algorithm also outperforms those of conventional techniques.
Perfect Secrecy Using Compressed Sensing
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we consider the compressed sensing-based encryption and proposed the conditions in which the perfect secrecy is obtained. We prove when the Restricted Isometery Property (RIP) is hold and the number of measurements is more than two times of sparsity level i.e. M \geq 2k, the perfect secrecy condition introduced by Shannon is achievable if message block is not equal to zero or we have infinite block length
Algorithms for enumerating and counting D2CS of some graphs
Venue: arXiv cs.DM 2010
Year: 2010

A D2CS of a graph G is a set $S \subseteq V(G)$ with $diam(G[S]) \leq 2$. We study the problem of counting and enumerating D2CS of a graph. First we give an explicit formula for the number of D2CS in a complete k-ary tree, Fibonacci tree, binary Fibonacci tree and the binomial tree. Next we give an algorithm for enumerating and counting D2CS of a graph. We then give a linear time algorithm for finding all maximal D2CS in a strongly chordal graph.
Complexity of Homogeneous Co-Boolean Constraint Satisfaction Problems
Venue: arXiv cs.CC 2010
Year: 2010

Constraint Satisfaction Problems (CSP) constitute a convenient way to capture many combinatorial problems. The general CSP is known to be NP-complete, but its complexity depends on a template, usually a set of relations, upon which they are constructed. Following this template, there exist tractable and intractable instances of CSPs. It has been proved that for each CSP problem over a given set of relations there exists a corresponding CSP problem over graphs of unary functions belonging to the same complexity class. In this short note we show a dichotomy theorem for every finite domain D of CSP built upon graphs of homogeneous co-Boolean functions, i.e., unary functions sharing the Boolean range {0, 1}.
Pair-wise Markov Random Fields Applied to the Design of Low Complexity MIMO Detectors
Venue: arXiv cs.IT 2010
Year: 2010

Pair-wise Markov random fields (MRF) are considered for application to the development of low complexity, iterative MIMO detection. Specifically, we consider two types of MRF, namely, the fully-connected and ring-type. For the edge potentials, we use the bivariate Gaussian function obtained by marginalizing the posterior joint probability density under the Gaussian assumption. Since the corresponding factor graphs are sparse, in the sense that the number of edges connected to a factor node (edge degree) is only 2, the computations are much easier than that of ML, which is similar to the belief propagation (BP), or sum-product, algorithm that is run over the fully connected factor graph. The BER performances for non-Gaussian input are evaluated via simulation, and the results show the validity of the proposed algorithms. We also customize the algorithm for Gaussian input to obtain the Gaussian BP that is run over the two MRF and proves its convergence in mean to the linear MMSE estimates. The result lies on the same line of those in [16] and [24], but with differences in its graphical model and the message passing rule. Since the MAP estimator for the Gaussian input is equivalent to the linear MMSE estimator, it shows the optimality, in mean, of the scheme for Gaussian input.
Optimal Placement Algorithms for Virtual Machines
Venue: arXiv cs.DC 2010
Year: 2010

Cloud computing provides a computing platform for the users to meet their demands in an efficient, cost-effective way. Virtualization technologies are used in the clouds to aid the efficient usage of hardware. Virtual machines (VMs) are utilized to satisfy the user needs and are placed on physical machines (PMs) of the cloud for effective usage of hardware resources and electricity in the cloud. Optimizing the number of PMs used helps in cutting down the power consumption by a substantial amount. In this paper, we present an optimal technique to map virtual machines to physical machines (nodes) such that the number of required nodes is minimized. We provide two approaches based on linear programming and quadratic programming techniques that significantly improve over the existing theoretical bounds and efficiently solve the problem of virtual machine (VM) placement in data centers.
Utility Constrained Energy Minimization In Aloha Networks
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we consider the issue of energy efficiency in random access networks and show that optimizing transmission probabilities of nodes can enhance network performance in terms of energy consumption and fairness. First, we propose a heuristic power control method that improves throughput, and then we model the Utility Constrained Energy Minimization (UCEM) problem in which the utility constraint takes into account single and multi node performance. UCEM is modeled as a convex optimization problem and Sequential Quadratic Programming (SQP) is used to find optimal transmission probabilities. Numerical results show that our method can achieve fairness, reduce energy consumption and enhance lifetime of such networks.
Covered Clause Elimination
Venue: arXiv cs.LO 2010
Year: 2010

Generalizing the novel clause elimination procedures developed in [M. Heule, M. Järvisalo, and A. Biere. Clause elimination procedures for CNF formulas. In Proc. LPAR-17, volume 6397 of LNCS, pages 357-371. Springer, 2010.], we introduce explicit (CCE), hidden (HCCE), and asymmetric (ACCE) variants of a procedure that eliminates covered clauses from CNF formulas. We show that these procedures are more effective in reducing CNF formulas than the respective variants of blocked clause elimination, and may hence be interesting as new preprocessing/simplification techniques for SAT solving.
Optimizing On-Line Advertising
Venue: arXiv cs.IR 2010
Year: 2010

We want to find the optimal strategy for displaying advertisements e.g. banners, videos, in given locations at given times under some realistic dynamic constraints. Our primary goal is to maximize the expected revenue in a given period of time, i.e. the total profit produced by the impressions, which depends on profit-generating events such as the impressions themselves, the ensuing clicks and registrations. Moreover we must take into consideration the possibility that the constraints could change in time in a way that cannot always be foreseen.
Image Inpainting Using Sparsity of the Transform Domain
Venue: arXiv cs.MM 2010
Year: 2010

In this paper, we propose a new image inpainting method based on the property that much of the image information in the transform domain is sparse. We add a redundancy to the original image by mapping the transform coefficients with small amplitudes to zero and the resultant sparsity pattern is used as the side information in the recovery stage. If the side information is not available, the receiver has to estimate the sparsity pattern. At the end, the recovery is done by consecutive projecting between two spatial and transform sets. Experimental results show that our method works well for both structural and texture images and outperforms other techniques in objective and subjective performance measures.
Simulating space and time
Venue: arXiv cs.OH 2010
Year: 2010

This chapter asks if a virtual space-time could appear to those within it as our space-time does to us. A processing grid network is proposed to underlie not just matter and energy, but also space and time. The suggested "screen" for our familiar three dimensional world is a hyper-sphere surface simulated by a grid network. Light and matter then travel, or are transmitted, in the "directions" of the grid architecture. The processing sequences of grid nodes create time, as the static states of movies run together emulate events. Yet here what exists are not the static states, but the dynamic processing between them. Quantum collapse is the irreversible event that gives time its direction. In this model, empty space is null processing, directions are node links, time is processing cycles, light is a processing wave, objects are wave tangles and energy is the processing transfer rate. It describes a world where empty space is not empty, space warps, time dilates, and everything began when this virtual universe "booted up".
Correlated Resource Models of Internet End Hosts
Venue: arXiv cs.DC 2010
Year: 2010

Understanding and modelling resources of Internet end hosts is essential for the design of desktop software and Internet-distributed applications. In this paper we develop a correlated resource model of Internet end hosts based on real trace data taken from the SETI@home project. This data covers a 5-year period with statistics for 2.7 million hosts. The resource model is based on statistical analysis of host computational power, memory, and storage as well as how these resources change over time and the correlations between them. We find that resources with few discrete values (core count, memory) are well modeled by exponential laws governing the change of relative resource quantities over time. Resources with a continuous range of values are well modeled with either correlated normal distributions (processor speed for integer operations and floating point operations) or log-normal distributions (available disk space). We validate and show the utility of the models by applying them to a resource allocation problem for Internet-distributed applications, and demonstrate their value over other models. We also make our trace data and tool for automatically generating realistic Internet end hosts publicly available.
Dynamic Power Allocation Games in Parallel Multiple Access Channels
Venue: arXiv cs.GT 2010
Year: 2010

We analyze the distributed power allocation problem in parallel multiple access channels (MAC) by studying an associated non-cooperative game which admits an exact potential. Even though games of this type have been the subject of considerable study in the literature, we find that the sufficient conditions which ensure uniqueness of Nash equilibrium points typically do not hold in this context. Nonetheless, we show that the parallel MAC game admits a unique equilibrium almost surely, thus establishing an important class of counterexamples where these sufficient conditions are not necessary. Furthermore, if the network's users employ a distributed learning scheme based on the replicator dynamics, we show that they converge to equilibrium from almost any initial condition, even though users only have local information at their disposal.
Decision Support Systems - Technical Prerequisites and Military Requirements
Venue: arXiv cs.OH 2010
Year: 2010

Decision Support Systems in the sense of online alternative course of action (ACAO) development and analysis as well as tools for online Development of Doctrine and Tactics Techniques, and Procedures (DTTP) for support to operations make it possible to evaluate and forecast the command and control processes and the performance capabilities of the friendly and enemy forces and other decision relevant factors, support the military commander (brigade and higher) and his staff in their headquarter by increasing their ability to identify own opportunities, support all phases of the command and control process, use computer based, automatic and closed models, that can be adapted to the current situation. Objective of the paper is to present the results of studies conducted in Germany on behalf of the German Ministry of Defense with the objective to work out the conceptual basis for decision support systems and to evaluate, how this technique will influence the command and control system of the army of the federal armed forces. In addition, international works are considered as well. In this paper, technical and operational requirements are derived and described in detail that have to be met in order to support the warfighter by integrated means of applied Operations Research ranging from simple optimization algorithms to complex simulation federations comprising different systems.
Reinforcement Learning in Partially Observable Markov Decision Processes using Hybrid Probabilistic Logic Programs
Venue: arXiv cs.AI 2010
Year: 2010

We present a probabilistic logic programming framework to reinforcement learning, by integrating reinforce-ment learning, in POMDP environments, with normal hybrid probabilistic logic programs with probabilistic answer set seman-tics, that is capable of representing domain-specific knowledge. We formally prove the correctness of our approach. We show that the complexity of finding a policy for a reinforcement learning problem in our approach is NP-complete. In addition, we show that any reinforcement learning problem can be encoded as a classical logic program with answer set semantics. We also show that a reinforcement learning problem can be encoded as a SAT problem. We present a new high level action description language that allows the factored representation of POMDP. Moreover, we modify the original model of POMDP so that it be able to distinguish between knowledge producing actions and actions that change the environment.
Performance Evaluation of the Labelled OBS Architecture
Venue: arXiv cs.NI 2010
Year: 2010

A comparison of three different Optical Burst Switching (OBS) architectures is made, in terms of performance criteria, control and hardware complexity, fairness, resource utilization, and burst loss probability. Regarding burst losses, we distinguish the losses due to burst contentions from those due to contentions of Burst Control Packets (BCP). The simulation results show that as a counterpart of an its additional hardware complexity, the labelled OBS (L-OBS) is an efficient OBS architecture compared to a Conventional OBS (C-OBS) as well as in comparison with Offset Time-Emulated OBS (E-OBS).
A framework to experiment optimizations for real-time and embedded software
Venue: arXiv cs.PF 2010
Year: 2010

Typical constraints on embedded systems include code size limits, upper bounds on energy consumption and hard or soft deadlines. To meet these requirements, it may be necessary to improve the software by applying various kinds of transformations like compiler optimizations, specific mapping of code and data in the available memories, code compression, etc. However, a transformation that aims at improving the software with respect to a given criterion might engender side effects on other criteria and these effects must be carefully analyzed. For this purpose, we have developed a common framework that makes it possible to experiment various code transfor-mations and to evaluate their impact of various criteria. This work has been carried out within the French ANR MORE project.
Video Stippling
Venue: arXiv cs.GR 2010
Year: 2010

In this paper, we consider rendering color videos using a non-photo-realistic art form technique commonly called stippling. Stippling is the art of rendering images using point sets, possibly with various attributes like sizes, elementary shapes, and colors. Producing nice stippling is attractive not only for the sake of image depiction but also because it yields a compact vectorial format for storing the semantic information of media. Moreover, stippling is by construction easily tunable to various device resolutions without suffering from bitmap sampling artifacts when resizing. The underlying core technique for stippling images is to compute a centroidal Voronoi tessellation on a well-designed underlying density. This density relates to the image content, and is used to compute a weighted Voronoi diagram. By considering videos as image sequences and initializing properly the stippling of one image by the result of its predecessor, one avoids undesirable point flickering artifacts and can produce stippled videos that nevertheless still exhibit noticeable artifacts. To overcome this, our method improves over the naive scheme by considering dynamic point creation and deletion according to the current scene semantic complexity, and show how to effectively vectorize video while adjusting for both color and contrast characteristics. Furthermore, we explain how to produce high quality stippled ``videos'' (eg., fully dynamic spatio-temporal point sets) for media containing various fading effects, like quick motions of objects or progressive shot changes. We report on practical performances of our implementation, and present several stippled video results rendered on-the-fly using our viewer that allows both spatio-temporal dynamic rescaling (eg., upscale vectorially frame rate).
Adapting MAC 802.11 Adapting MAC 802.11 for Performance Optimization of MANET using Cross Layer Interaction
Venue: arXiv cs.NI 2010
Year: 2010

In this research, we study the optimization challenges of MANET and cross-layer technique to improve its performance. We propose an adaptive retransmission limits algorithm for IEEE 802.11 MAC to reduce the false link failures and predict the node mobility. We implemented cross layer interaction between physical and MAC layers. The MAC layer utilizes the physical layer information for differentiating false link failure from true link failure. The MAC layer adaptively selects a retransmission limit (short and long) based on the neighbour signal strength and sender node speed information from the physical layer. The proposed approach tracks the signal strength of each node in network and, while transmitting to a neighbour node, if it's received signal strength is high and is received recently then Adaptive MAC persists in its retransmission attempts. As there is high probability that neighbour node is still in transmission range and may be not responding due to some problems other then mobility. In this paper, we evaluate the performance of MANET and show that how our Adaptive MAC greatly improves it. The simulation is done using Network Simulator NS-2.