Kristóf Bérczi, Endre Boros, Ondřej Čepek, Petr Kučera, Kazuhisa Makino
2018-11-13
Horn functions form a subclass of Boolean functions and appear in many different areas of computer science and mathematics as a general tool to describe implications and dependencies. Finding minimum sized representations for such functions with respect to most commonly used measures is a computationally hard problem that remains hard even for the important subclass of key Horn functions. In this paper we provide logarithmic factor approximation algorithms for key Horn functions with respect to all measures studied in the literature for which the problem is known to be hard.
Sebastian Brandt, Klaus-Tycho Foerster, Jonathan Maurer, Roger Wattenhofer
2019-03-01
We study the problem of online graph exploration on undirected graphs, where a searcher has to visit every vertex and return to the origin. Once a new vertex is visited, the searcher learns of all neighboring vertices and the connecting edge weights. The goal such an exploration is to minimize its total cost, where each edge traversal incurs a cost of the corresponding edge weight. We investigate the problem on tadpole graphs (also known as dragons, kites), which consist of a cycle with an attached path. Miyazaki et al. (The online graph exploration problem on restricted graphs, IEICE Transactions 92-D (9), 2009) showed that every online algorithm on these graphs must have a competitive ratio of 2-epsilon, but did not provide upper bounds for non-unit edge weights. We show via amortized analysis that a greedy approach yields a matching competitive ratio of 2 on tadpole graphs, for arbitrary non-negative edge weights.
Let and be two point sets in the plane of sizes and respectively (assume ), and let be a parameter. A matching between and is a family of pairs in so that any point of appears in at most one pair. Given two positive integers and , we define the cost of matching to be where is the -norm. The geometric partial matching problem asks to find the minimum-cost size- matching between and . We present efficient algorithms for geometric partial matching problem that work for any powers of -norm matching objective: An exact algorithm that runs in time, and a -approximation algorithm that runs in time. Both algorithms are based on the primal-dual flow augmentation scheme; the main improvements involve using dynamic data structures to achieve efficient flow augmentations. With similar techniques, we give an exact algorithm for the planar transportation problem running in time.
We present an approach that improves the sample complexity for a variety of curve fitting problems, including active learning for linear regression, polynomial regression, and continuous sparse Fourier transforms. In the active linear regression problem, one would like to estimate the least squares solution minimizing given the entire unlabeled dataset but only observing a small number of labels . We show that labels suffice to find a constant factor approximation : [ \mathbb{E}[|X\tilde{\beta} - y|_2^2] \leq 2 \mathbb{E}[|X \beta^* - y|_2^2]. ] This improves on the best previous result of from leverage score sampling. We also present results for the \emph{inductive} setting, showing when will generalize to fresh samples; these apply to continuous settings such as polynomial regression. Finally, we show how the techniques yield improved results for the non-linear sparse Fourier transform setting.
String attractors are a novel combinatorial object encompassing most known compressibility measures for highly-repetitive texts. Recently, the first index building on an attractor of size of a text was obtained. It uses space and finds the occurrences of a pattern in time for any constant . We now show how to reduce the search time to within the same space, and ultimately obtain the optimal time within space. Further, we show how to count the number of occurrences of in time within space, or the optimal time within space. These turn out to be the first optimal-time indexes within grammar- and Lempel-Ziv-bounded space. As a byproduct of independent interest, we show how to build, in expected time and without knowing the size of the smallest attractor, a run-length context-free grammar of size generating (only) .
Panagiotis Charalampopoulos, Shay Mozes, Benjamin Tebeka
2018-07-16
We consider exact distance oracles for directed weighted planar graphs in the presence of failing vertices. Given a source vertex , a target vertex and a set of failed vertices, such an oracle returns the length of a shortest -to- path that avoids all vertices in . We propose oracles that can handle any number of failures. More specifically, for a directed weighted planar graph with vertices, any constant , and for any , we propose an oracle of size that answers queries in time. In particular, we show an -size, -query-time oracle for any constant . This matches, up to polylogarithmic factors, the fastest failure-free distance oracles with nearly linear space. For single vertex failures (), our -size, -query-time oracle improves over the previously best known tradeoff of Baswana et al. [SODA 2012] by polynomial factors for , . For multiple failures, no planarity exploiting results were previously known.
This work presents an empirical analysis of exact algorithms for the unbounded knapsack problem, which includes seven algorithms from the literature, two commercial solvers, and more than ten thousand instances. The terminating step-off, a dynamic programming algorithm from 1966, presented the lowest mean time to solve the most recent benchmark from the literature. The threshold and collective dominances are properties of the unbounded knapsack problem first discussed in 1998, and exploited by the current state-of-the-art algorithms. The terminating step-off algorithm did not exploit such dominances, but has an alternative mechanism for dealing with dominances which does not explicitly exploits collective and threshold dominances. Also, the pricing subproblems found when solving hard cutting stock problems with column generation can cause branch-and-bound algorithms to display worst-case times. The authors present a new class of instances which favors the branch-and-bound approach over the dynamic programming approach but do not have high amounts of simple, multiple and collective dominated items. This behaviour illustrates how the definition of hard instances changes among algorithm approachs. The codes used for solving the unbounded knapsack problem and for instance generation are all available online.
In the -cut problem, we are given an edge-weighted graph and an integer , and have to remove a set of edges with minimum total weight so that has at least connected components. The current best algorithms are an randomized algorithm due to Karger and Stein, and an deterministic algorithm due to Thorup. Moreover, several -approximation algorithms are known for the problem (due to Saran and Vazirani, Naor and Rabani, and Ravi and Sinha). It has remained an open problem to (a) improve the runtime of exact algorithms, and (b) to get better approximation algorithms. In this paper we show an -time algorithm for -cut. Moreover, we show an -approximation algorithm that runs in time , and a -approximation in fixed-parameter time .
Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala
2019-03-21
With the rapid growth of graph datasets over the past decade, a new kind of dynamic algorithm, supporting the ability to ingest batches of updates and exploit parallelism is needed in order to efficiently process large streams of updates. In this paper, we study batch and parallel algorithms for the dynamic connectivity problem, a fundamental problem that has received considerable attention in sequential setting. Perhaps the best known sequential algorithm is the elegant level-set algorithm of Holm, de Lichtenberg and Thorup (HDT), which achieves amortized time per edge insertion or deletion, and time per query. In this paper, we design a parallel batch-dynamic connectivity algorithm that is work-efficient with respect to the HDT algorithm for small batch sizes, and is asymptotically faster when the average batch size is sufficiently large. Given a sequence of batched updates, where is the average batch size of all deletions, our algorithm achieves expected amortized work per edge insertion and deletion and depth w.h.p. Our algorithm answers a batch of connectivity queries in expected work and depth w.h.p. To the best of our knowledge, our algorithm is the first parallel batch-dynamic algorithm for connectivity.
We give offline algorithms for processing a sequence of and edge and vertex connectivity queries in a fully-dynamic undirected graph. While the current best fully-dynamic online data structures for -edge and -vertex connectivity require and time per update, respectively, our per-operation cost is only , optimal due to the dynamic connectivity lower bound of Patrascu and Demaine. Our approach utilizes a divide and conquer scheme that transforms a graph into smaller equivalents that preserve connectivity information. This construction of equivalents is closely-related to the development of vertex sparsifiers, and shares important connections to several upcoming results in dynamic graph data structures, outside of just the offline model.
Data Structures And Algorithms | 2019-03-26 | Ecency
