OpenRaiser/Intern-Atlas huggingface dataset:
Approximation Algorithms for the Joint Replenishment Problem with Deadlines
Venue: arXiv cs.DS 2015
Year: 2015

The Joint Replenishment Problem (JRP) is a fundamental optimization problem in supply-chain management, concerned with optimizing the flow of goods from a supplier to retailers. Over time, in response to demands at the retailers, the supplier ships orders, via a warehouse, to the retailers. The objective is to schedule these orders to minimize the sum of ordering costs and retailers' waiting costs. We study the approximability of JRP-D, the version of JRP with deadlines, where instead of waiting costs the retailers impose strict deadlines. We study the integrality gap of the standard linear-program (LP) relaxation, giving a lower bound of 1.207, a stronger, computer-assisted lower bound of 1.245, as well as an upper bound and approximation ratio of 1.574. The best previous upper bound and approximation ratio was 1.667; no lower bound was previously published. For the special case when all demand periods are of equal length we give an upper bound of 1.5, a lower bound of 1.2, and show APX-hardness.
Two-Dimensional Kolmogorov Complexity and Validation of the Coding Theorem Method by Compressibility
Venue: arXiv cs.CC 2015
Year: 2015

We propose a measure based upon the fundamental theoretical concept in algorithmic information theory that provides a natural approach to the problem of evaluating $n$-dimensional complexity by using an $n$-dimensional deterministic Turing machine. The technique is interesting because it provides a natural algorithmic process for symmetry breaking generating complex $n$-dimensional structures from perfectly symmetric and fully deterministic computational rules producing a distribution of patterns as described by algorithmic probability. Algorithmic probability also elegantly connects the frequency of occurrence of a pattern with its algorithmic complexity, hence effectively providing estimations to the complexity of the generated patterns. Experiments to validate estimations of algorithmic complexity based on these concepts are presented, showing that the measure is stable in the face of some changes in computational formalism and that results are in agreement with the results obtained using lossless compression algorithms when both methods overlap in their range of applicability. We then use the output frequency of the set of 2-dimensional Turing machines to classify the algorithmic complexity of the space-time evolutions of Elementary Cellular Automata.
Regular Bipartite Graphs And Their Properties
Venue: arXiv cs.DM 2015
Year: 2015

We introduce a new notation for representing labeled regular bipartite graphs of arbitrary degree. Several enumeration problems for labeled and unlabeled regular bipartite graphs have been introduced. A general algorithm for enumerating all non-isomorphic 2-regular bipartite graphs for a specified number of vertices has been described and a mathematical proof has been provided for its completeness. An abstraction of m Symmetric Permutation Tree in order to visualize a labeled r-Regular Bipartite Graph with 2m vertices and enumerate its automorphism group has been introduced. An algorithm to generate the partition associated with two compatible permutations has been introduced. The relationship between Automorphism Group and permutation enumeration problem has been used to derive formulae for the number of compatible permutations corresponding to a specified partition.
An MDP-based Recommender System
Venue: arXiv cs.LG 2015
Year: 2015

Typical Recommender systems adopt a static view of the recommendation process and treat it as a prediction problem. We argue that it is more appropriate to view the problem of generating recommendations as a sequential decision problem and, consequently, that Markov decision processes (MDP) provide a more appropriate model for Recommender systems. MDPs introduce two benefits: they take into account the long-term effects of each recommendation, and they take into account the expected value of each recommendation. To succeed in practice, an MDP-based Recommender system must employ a strong initial model; and the bulk of this paper is concerned with the generation of such a model. In particular, we suggest the use of an n-gram predictive model for generating the initial MDP. Our n-gram model induces a Markov-chain model of user behavior whose predictive accuracy is greater than that of existing predictive models. We describe our predictive model in detail and evaluate its performance on real data. In addition, we show how the model can be used in an MDP-based Recommender system.
Good parts first - a new algorithm for approximate search in lexica and string databases
Venue: arXiv cs.CL 2015
Year: 2015

We present a new efficient method for approximate search in electronic lexica. Given an input string (the pattern) and a similarity threshold, the algorithm retrieves all entries of the lexicon that are sufficiently similar to the pattern. Search is organized in subsearches that always start with an exact partial match where a substring of the input pattern is aligned with a substring of a lexicon word. Afterwards this partial match is extended stepwise to larger substrings. For aligning further parts of the pattern with corresponding parts of lexicon entries, more errors are tolerated at each subsequent step. For supporting this alignment order, which may start at any part of the pattern, the lexicon is represented as a structure that enables immediate access to any substring of a lexicon word and permits the extension of such substrings in both directions. Experimental evaluations of the approximate search procedure are given that show significant efficiency improvements compared to existing techniques. Since the technique can be used for large error bounds it offers interesting possibilities for approximate search in special collections of "long" strings, such as phrases, sentences, or book ti
A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
Venue: arXiv cs.LG 2015
Year: 2015

Linear optimization is many times algorithmically simpler than non-linear convex optimization. Linear optimization over matroid polytopes, matching polytopes and path polytopes are example of problems for which we have simple and efficient combinatorial algorithms, but whose non-linear convex counterpart is harder and admits significantly less efficient algorithms. This motivates the computational model of convex optimization, including the offline, online and stochastic settings, using a linear optimization oracle. In this computational model we give several new results that improve over the previous state-of-the-art. Our main result is a novel conditional gradient algorithm for smooth and strongly convex optimization over polyhedral sets that performs only a single linear optimization step over the domain on each iteration and enjoys a linear convergence rate. This gives an exponential improvement in convergence rate over previous results. Based on this new conditional gradient algorithm we give the first algorithms for online convex optimization over polyhedral sets that perform only a single linear optimization step over the domain while having optimal regret guarantees, answering an open question of Kalai and Vempala, and Hazan and Kale. Our online algorithms also imply conditional gradient algorithms for non-smooth and stochastic convex optimization with the same convergence rates as projected (sub)gradient methods.
Relative Generalized Rank Weight of Linear Codes and Its Applications to Network Coding
Venue: arXiv cs.IT 2015
Year: 2015

By extending the notion of minimum rank distance, this paper introduces two new relative code parameters of a linear code C_1 of length n over a field extension and its subcode C_2. One is called the relative dimension/intersection profile (RDIP), and the other is called the relative generalized rank weight (RGRW). We clarify their basic properties and the relation between the RGRW and the minimum rank distance. As applications of the RDIP and the RGRW, the security performance and the error correction capability of secure network coding, guaranteed independently of the underlying network code, are analyzed and clarified. We propose a construction of secure network coding scheme, and analyze its security performance and error correction capability as an example of applications of the RDIP and the RGRW. Silva and Kschischang showed the existence of a secure network coding in which no part of the secret message is revealed to the adversary even if any dim C_1-1 links are wiretapped, which is guaranteed over any underlying network code. However, the explicit construction of such a scheme remained an open problem. Our new construction is just one instance of secure network coding that solves this open problem.
Lower bounds for the circuit size of partially homogeneous polynomials
Venue: arXiv cs.CC 2015
Year: 2015

In this paper we associate to each multivariate polynomial $f$ that is homogeneous relative to a subset of its variables a series of polynomial families $P_λ(f)$ of $m$-tuples of homogeneous polynomials of equal degree such that the circuit size of any member in $P_λ(f)$ is bounded from above by the circuit size of $f$. This provides a method for obtaining lower bounds for the circuit size of $f$ by proving $(s,r)$-(weak) elusiveness of the polynomial mapping associated with $P_λ(f)$. We discuss some algebraic methods for proving the $(s,r)$-(weak) elusiveness. We also improve estimates in the normal homogeneous-form of an arithmetic circuit obtained by Raz in \cite{Raz2009} which results in better lower bounds for circuit size (Lemma \ref{lem:cor38}, Remark \ref{rem:cor38}). Our methods yield non-trivial lower bound for the circuit size of several classes of multivariate homogeneous polynomials (Corollary \ref{cor:412}, Example \ref{ex:bi}).
An Efficient Implementation of the Ensemble Kalman Filter Based on an Iterative Sherman-Morrison Formula
Venue: arXiv cs.NA 2015
Year: 2015

We present a practical implementation of the ensemble Kalman (EnKF) filter based on an iterative Sherman-Morrison formula. The new direct method exploits the special structure of the ensemble-estimated error covariance matrices in order to efficiently solve the linear systems involved in the analysis step of the EnKF. The computational complexity of the proposed implementation is equivalent to that of the best EnKF implementations available in the literature when the number of observations is much larger than the number of ensemble members. Even when this conditions is not fulfilled, the proposed method is expected to perform well since it does not employ matrix decompositions. Computational experiments using the Lorenz 96 and the oceanic quasi-geostrophic models are performed in order to compare the proposed algorithm with EnKF implementations that use matrix decompositions. In terms of accuracy, the results of all implementations are similar. The proposed method is considerably faster than other EnKF variants, even when the number of observations is large relative to the number of ensemble members.
Kernelization Using Structural Parameters on Sparse Graph Classes
Venue: arXiv cs.DS 2015
Year: 2015

Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, meta-theorems for linear kernels exist on graphs of bounded genus, $H$-minor-free graphs, and $H$-topological-minor-free graphs. To the best of our knowledge, no meta-theorems for polynomial kernels are known for any larger sparse graph classes; e.g., for classes of bounded expansion or for nowhere dense ones. In this paper we prove such meta-theorems for the two latter cases. More specifically, we show that graph problems that have finite integer index (FII) have linear kernels on graphs of bounded expansion when parameterized by the size of a modulator to constant-treedepth graphs. For nowhere dense graph classes, our result yields almost-linear kernels. While our parameter may seem rather strong, we argue that a linear kernelization result on graphs of bounded expansion with a weaker parameter (than treedepth modulator) would fail to include some of the problems covered by our framework. Moreover, we only require the problems to have FII on graphs of constant treedepth. This allows us to prove linear kernels for problems such as Longest Path/Cycle, Exact $s,t$-Path, Treewidth, and Pathwidth, which do not have FII on general graphs (and the first two not even on bounded treewidth graphs).
The Second-Order Coding Rate of the MIMO Rayleigh Block-Fading Channel
Venue: arXiv cs.IT 2015
Year: 2015

The second-order coding rate of the multiple-input multiple-output (MIMO) quasi-static Rayleigh fading channel is studied. We tackle this problem via an information-spectrum approach and statistical bounds based on recent random matrix theory techniques. We derive a central limit theorem (CLT) to analyze the information density in the regime where the block-length n and the number of transmit and receive antennas K and N, respectively, grow simultaneously large. This result leads to the characterization of closed-form upper and lower bounds on the optimal average error probability when the coding rate is within O((nK)^-1/2) of the asymptotic capacity.
Ultra-fast Multiple Genome Sequence Matching Using GPU
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, a contrastive evaluation of massively parallel implementations of suffix tree and suffix array to accelerate genome sequence matching are proposed based on Intel Core i7 3770K quad-core and NVIDIA GeForce GTX680 GPU. Besides suffix array only held approximately 20%~30% of the space relative to suffix tree, the coalesced binary search and tile optimization make suffix array clearly outperform suffix tree using GPU. Consequently, the experimental results show that multiple genome sequence matching based on suffix array is more than 99 times speedup than that of CPU serial implementation. There is no doubt that massively parallel matching algorithm based on suffix array is an efficient approach to high-performance bioinformatics applications.
Multi-dimensional sparse structured signal approximation using split Bregman iterations
Venue: arXiv cs.DS 2015
Year: 2015

The paper focuses on the sparse approximation of signals using overcomplete representations, such that it preserves the (prior) structure of multi-dimensional signals. The underlying optimization problem is tackled using a multi-dimensional split Bregman optimization approach. An extensive empirical evaluation shows how the proposed approach compares to the state of the art depending on the signal features.
Optimal Partitioning for Dual-Pivot Quicksort
Venue: arXiv cs.DS 2015
Year: 2015

Dual-pivot quicksort refers to variants of classical quicksort where in the partitioning step two pivots are used to split the input into three segments. This can be done in different ways, giving rise to different algorithms. Recently, a dual-pivot algorithm proposed by Yaroslavskiy received much attention, because a variant of it replaced the well-engineered quicksort algorithm in Sun's Java 7 runtime library. Nebel and Wild (ESA 2012) analyzed this algorithm and showed that on average it uses 1.9n ln n + O(n) comparisons to sort an input of size n, beating standard quicksort, which uses 2n ln n + O(n) comparisons. We introduce a model that captures all dual-pivot algorithms, give a unified analysis, and identify new dual-pivot algorithms that minimize the average number of key comparisons among all possible algorithms up to a linear term. This minimum is 1.8n ln n + O(n). For the case that the pivots are chosen from a small sample, we include a comparison of dual-pivot quicksort and classical quicksort. Specifically, we show that dual-pivot quicksort benefits from a skewed choice of pivots. We experimentally evaluate our algorithms and compare them to Yaroslavskiy's algorithm and the recently described three-pivot quicksort algorithm of Kushagra et al. (ALENEX 2014).
The Finite State MAC with Cooperative Encoders and Delayed CSI
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider the finite-state multiple access channel (MAC) with partially cooperative encoders and delayed channel state information (CSI). Here partial cooperation refers to the communication between the encoders via finite-capacity links. The channel states are assumed to be governed by a Markov process. Full CSI is assumed at the receiver, while at the transmitters, only delayed CSI is available. The capacity region of this channel model is derived by first solving the case of the finite-state MAC with a common message. Achievability for the latter case is established using the notion of strategies, however, we show that optimal codes can be constructed directly over the input alphabet. This results in a single codebook construction that is then leveraged to apply simultaneous joint decoding. Simultaneous decoding is crucial here because it circumvents the need to rely on the capacity region's corner points, a task that becomes increasingly cumbersome with the growth in the number of messages to be sent. The common message result is then used to derive the capacity region for the case with partially cooperating encoders. Next, we apply this general result to the special case of the Gaussian vector MAC with diagonal channel transfer matrices, which is suitable for modeling, e.g., orthogonal frequency division multiplexing (OFDM)-based communication systems. The capacity region of the Gaussian channel is presented in terms of a convex optimization problem that can be solved efficiently using numerical tools. The region is derived by first presenting an outer bound on the general capacity region and then suggesting a specific input distribution that achieves this bound. Finally, numerical results are provided that give valuable insight into the practical implications of optimally using conferencing to maximize the transmission rates.
Problem Formulation as the Reduction of a Decision Model
Venue: arXiv cs.AI 2015
Year: 2015

In this paper, we extend the QMRDT probabilistic model for the domain of internal medicine to include decisions about treatments. In addition, we describe how we can use the comprehensive decision model to construct a simpler decision model for a specific patient. In so doing, we transform the task of problem formulation to that of narrowing of a larger problem.
Sequential Randomized Algorithms for Convex Optimization in the Presence of Uncertainty
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we propose new sequential randomized algorithms for convex optimization problems in the presence of uncertainty. A rigorous analysis of the theoretical properties of the solutions obtained by these algorithms, for full constraint satisfaction and partial constraint satisfaction, respectively, is given. The proposed methods allow to enlarge the applicability of the existing randomized methods to real-world applications involving a large number of design variables. Since the proposed approach does not provide a priori bounds on the sample complexity, extensive numerical simulations, dealing with an application to hard-disk drive servo design, are provided. These simulations testify the goodness of the proposed solution.
The Stability of Delaunay Triangulations
Venue: arXiv cs.CG 2015
Year: 2015

We introduce a parametrized notion of genericity for Delaunay triangulations which, in particular, implies that the Delaunay simplices of $δ$-generic point sets are thick. Equipped with this notion, we study the stability of Delaunay triangulations under perturbations of the metric and of the vertex positions. We quantify the magnitude of the perturbations under which the Delaunay triangulation remains unchanged.
Geometry-driven collapses for converting a Cech complex into a triangulation of a nicely triangulable shape
Venue: arXiv cs.CG 2015
Year: 2015

Given a set of points that sample a shape, the Rips complex of the data points is often used in machine-learning to provide an approximation of the shape easily-computed. It has been proved recently that the Rips complex captures the homotopy type of the shape assuming the vertices of the complex meet some mild sampling conditions. Unfortunately, the Rips complex is generally high-dimensional. To remedy this problem, it is tempting to simplify it through a sequence of collapses. Ideally, we would like to end up with a triangulation of the shape. Experiments suggest that, as we simplify the complex by iteratively collapsing faces, it should indeed be possible to avoid entering a dead end such as the famous Bing's house with two rooms. This paper provides a theoretical justification for this empirical observation. We demonstrate that the Rips complex of a point-cloud (for a well-chosen scale parameter) can always be turned into a simplicial complex homeomorphic to the shape by a sequence of collapses, assuming the shape is nicely triangulable and well-sampled (two concepts we will explain in the paper). To establish our result, we rely on a recent work which gives conditions under which the Rips complex can be converted into a Cech complex by a sequence of collapses. We proceed in two phases. Starting from the Cech complex, we first produce a sequence of collapses that arrives to the Cech complex, restricted by the shape. We then apply a sequence of collapses that transforms the result into the nerve of some robust covering of the shape.
Another Asymptotic Notation : "Almost"
Venue: arXiv cs.CC 2015
Year: 2015

Asymptotic notations are heavily used while analysing runtimes of algorithms. Present paper argues that some of these usages are non trivial, therefore incurring errors in communication of ideas. After careful reconsidera- tion of the various existing notations a new notation is proposed. This notation has similarities with the other heavily used notations like Big-Oh, Big Theta, while being more accurate when describing the order relationship. It has been argued that this notation is more suitable for describing algorithm runtime than Big-Oh.
Synchronous Counting and Computational Algorithm Design
Venue: arXiv cs.DC 2015
Year: 2015

Consider a complete communication network on $n$ nodes, each of which is a state machine. In synchronous 2-counting, the nodes receive a common clock pulse and they have to agree on which pulses are "odd" and which are "even". We require that the solution is self-stabilising (reaching the correct operation from any initial state) and it tolerates $f$ Byzantine failures (nodes that send arbitrary misinformation). Prior algorithms are expensive to implement in hardware: they require a source of random bits or a large number of states. This work consists of two parts. In the first part, we use computational techniques (often known as synthesis) to construct very compact deterministic algorithms for the first non-trivial case of $f = 1$. While no algorithm exists for $n < 4$, we show that as few as 3 states per node are sufficient for all values $n \ge 4$. Moreover, the problem cannot be solved with only 2 states per node for $n = 4$, but there is a 2-state solution for all values $n \ge 6$. In the second part, we develop and compare two different approaches for synthesising synchronous counting algorithms. Both approaches are based on casting the synthesis problem as a propositional satisfiability (SAT) problem and employing modern SAT-solvers. The difference lies in how to solve the SAT problem: either in a direct fashion, or incrementally within a counter-example guided abstraction refinement loop. Empirical results suggest that the former technique is more efficient if we want to synthesise time-optimal algorithms, while the latter technique discovers non-optimal algorithms more quickly.