Data Structures And Algorithms | 2019-03-08
Data Structures And Algorithms
Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space (1903.02533v1)
J. Ian Munro, Sebastian Wild
2019-03-06
The range-minimum query (RMQ) problem is a fundamental data structuring task with numerous applications. Despite the fact that succinct solutions with worst-case optimal
bits of space and constant query time are known, it has been unknown whether such a data structure can be made adaptive to the reduced entropy of random inputs (Davoodi et al. 2014). We construct a succinct data structure with the optimal
bits of space on average for random RMQ instances, settling this open problem. Our solution relies on a compressed data structure for binary trees that is of independent interest. It can store a (static) binary search tree generated by random insertions in asymptotically optimal expected space and supports many queries in constant time. Using an instance-optimal encoding of subtrees, we furthermore obtain a "hyper-succinct" data structure for binary trees that improves upon the ultra-succinct representation of Jansson, Sadakane and Sung (2012).
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem (1902.06808v2)
Samuel C. Gutekunst, David P. Williamson
2019-02-18
We consider the integrality gap of the subtour LP relaxation of the Traveling Salesman Problem restricted to circulant instances. De Klerk and Dobre conjectured that the value of the optimal solution to the subtour LP on these instances is equal to an entirely combinatorial lower bound from Van der Veen, Van Dal, and Sierksma. We prove this conjecture by giving an explicit optimal solution to the subtour LP. We then use it to show that the integrality gap of the subtour LP is 2 on circulant instances, making such instances one of the few non-trivial classes of TSP instances for which the integrality gap of the subtour LP is exactly known. We also show that the degree constraints do not strengthen the subtour LP on circulant instances, mimicking the parsimonious property of metric, symmetric TSP instances shown in Goemans and Bertsimas in a distinctly non-metric set of instances.
Quantized Frank-Wolfe: Communication-Efficient Distributed Optimization (1902.06332v2)
Mingrui Zhang, Lin Chen, Aryan Mokhtari, Hamed Hassani, Amin Karbasi
2019-02-17
How can we efficiently mitigate the overhead of gradient communications in distributed optimization? This problem is at the heart of training scalable machine learning models and has been mainly studied in the unconstrained setting. In this paper, we propose Quantized Frank-Wolfe (QFW), the first projection-free and communication-efficient algorithm for solving constrained optimization problems at scale. We consider both convex and non-convex objective functions, expressed as a finite-sum or more generally a stochastic optimization problem, and provide strong theoretical guarantees on the convergence rate of QFW. This is done by proposing quantization schemes that efficiently compress gradients while controlling the variance introduced during this process. Finally, we empirically validate the efficiency of QFW in terms of communication and the quality of returned solution against natural baselines.
The Parameterized Complexity of Motion Planning for Snake-Like Robots (1903.02445v1)
Siddharth Gupta, Guy Sa'ar, Meirav Zehavi
2019-03-06
We study the parameterized complexity of a variant of the classic video game Snake that models real-world problems of motion planning. Given a snake-like robot with an initial position and a final position in an environment (modeled by a graph), our objective is to determine whether the robot can reach the final position from the initial position without intersecting itself. Naturally, this problem models a wide-variety of scenarios, ranging from the transportation of linked wagons towed by a locomotor at an airport or a supermarket to the movement of a group of agents that travel in an `ant-like' fashion and the construction of trains in amusement parks. Unfortunately, already on grid graphs, this problem is PSPACE-complete [Biasi and Ophelders, 2016]. Nevertheless, we prove that even on general graphs, the problem is solvable in time
where
is the size of the snake, and
is the input size. In particular, this shows that the problem is fixed-parameter tractable (FPT). Towards this, we show how to employ color-coding to sparsify the configuration graph of the problem to have size
. We believe that our approach will find other applications in motion planning. Additionally, we show that the problem is unlikely to admit a polynomial kernel even on grid graphs, but it admits a treewidth-reduction procedure. To the best of our knowledge, the study of the parameterized complexity of motion planning problems (where the intermediate configurations of the motion are of importance) has so far been largely overlooked. Thus, our work is pioneering in this regard.
Bounded Dijkstra (BD): Search Space Reduction for Expediting Shortest Path Subroutines (1903.00436v2)
Amaury Van Bemten, Jochen W. Guck, Carmen Mas Machuca, Wolfgang Kellerer
2019-03-01
The shortest path (SP) and shortest paths tree (SPT) problems arise both as direct applications and as subroutines of overlay algorithms solving more complex problems such as the constrained shortest path (CSP) or the constrained minimum Steiner tree (CMST) problems. Often, such algorithms do not use the result of an SP subroutine if its total cost is greater than a given bound. For example, for delay-constrained problems, paths resulting from a least-delay SP run and whose delay is greater than the delay constraint of the original problem are not used by the overlay algorithm to construct its solution. As a result of the existence of these bounds, and because the Dijkstra SP algorithm discovers paths in increasing order of cost, we can terminate the SP search earlier, i.e., once it is known that paths with a greater total cost will not be considered by the overlay algorithm. This early termination allows to reduce the runtime of the SP subroutine, thereby reducing the runtime of the overlay algorithm without impacting its final result. We refer to this adaptation of Dijkstra for centralized implementations as bounded Dijkstra (BD). On the example of CSP algorithms, we confirm the usefulness of BD by showing that it can reduce the runtime of some algorithms by 75% on average.
Space-efficient merging of succinct de Bruijn graphs (1902.02889v3)
Lavinia Egidi, Felipe A. Louza, Giovanni Manzini
2019-02-07
We propose a new algorithm for merging succinct representations of de Bruijn graphs introduced in [Bowe et al. WABI 2012]. Our algorithm is based on the lightweight BWT merging approach by Holt and McMillan [Bionformatics 2014, ACM-BCB 2014]. Our algorithm has the same asymptotic cost of the state of the art tool for the same problem presented by Muggli et al. [bioRxiv 2017, 2019], but it is more space efficient. A novel feature of our algorithm not found in the existing tools is that it can compute the Variable Order succinct representation of the union graph starting from the plain representation of the input graphs.
Runtime Analysis of RLS and (1+1) EA for the Dynamic Weighted Vertex Cover Problem (1903.02195v1)
Mojgan Pourhassan, Vahid Roostapour, Frank Neumann
2019-03-06
In this paper, we perform theoretical analyses on the behaviour of an evolutionary algorithm and a randomised search algorithm for the dynamic vertex cover problem based on its dual formulation. The dynamic vertex cover problem has already been theoretically investigated to some extent and it has been shown that using its dual formulation to represent possible solutions can lead to a better approximation behaviour. We improve some of the existing results, i.e. we find a linear expected re-optimization time for a (1+1) EA to re-discover a 2-approximation when edges are dynamically deleted from the graph. Furthermore, we investigate a different setting for applying the dynamism to the problem, in which a dynamic change happens at each step with a probability
. We also expand these analyses to the weighted vertex cover problem, in which weights are assigned to vertices and the goal is to find a cover set with minimum total weight. Similar to the classical case, the dynamic changes that we consider on the weighted vertex cover problem are adding and removing edges to and from the graph. We aim at finding a maximal solution for the dual problem, which gives a 2-approximate solution for the vertex cover problem. This is equivalent to the maximal matching problem for the classical vertex cover problem.
Stable Noncrossing Matchings (1903.02185v1)
Suthee Ruangwises, Toshiya Itoh
2019-03-06
Given a set of
men represented by
is a pair
of a man and a woman such that they are not matched with each other but prefer each other to their own partners in
algorithm to find one in a given instance.
An Efficient Algorithm for Enumerating Chordal Bipartite Induced Subgraphs in Sparse Graphs (1903.02161v1)
Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
2019-03-06
In this paper, we propose a characterization of chordal bipartite graphs and an efficient enumeration algorithm for chordal bipartite induced subgraphs. A chordal bipartite graph is a bipartite graph without induced cycles with length six or more. It is known that the incident graph of a hypergraph is chordal bipartite graph if and only if the hypergraph is
-acyclic. As the main result of our paper, we show that a graph
is chordal bipartite if and only if there is a special vertex elimination ordering for
time per solution on average, where
is the maximum size of
as an induced subgraph, and
is the degree. ECB achieves constant amortized time enumeration for bounded degree graphs.
On the Convergence of Network Systems (1902.04121v2)
Evangelos Kipouridis, Kostas Tsichlas
2019-02-11
The apparent disconnection between the microscopic and the macroscopic is a major issue in the understanding of complex systems. To this extend, we study the convergence of repeatedly applying local rules on a network, and touch on the expressive power of this model. We look at network systems and study their behavior when different types of local rules are applied on them. For a very general class of local rules, we prove convergence and provide a certain member of this class that, when applied on a graph, efficiently computes its k-core and its (k-1)-crust giving hints on the expressive power of such a model. Furthermore, we provide guarantees on the speed of convergence for an important subclass of the aforementioned class. We also study more general rules, and show that they do not converge. Our counterexamples resolve an open question of (Zhang, Wang, Wang, Zhou, KDD- 2009) as well, concerning whether a certain process converges. Finally, we show the universality of our network system, by providing a local rule under which it is Turing-Complete.