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.
Henrique Becker, Luciana S. Buriol
2019-03-21
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.
Anupam Gupta, Euiwoong Lee, Jason Li
2018-07-21
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.
Richard Peng, Bryce Sandlund, Daniel D. Sleator
2017-08-12
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.
Rafael Araujo, Sulamita Klein, Rudini Sampaio, Ueverton S. Souza
2018-10-18
Given a graph
, let and be the sizes of a minimum and a maximum minimal vertex covers of , respectively. We say that is well covered if (that is, all minimal vertex covers have the same size). Determining if a graph is well covered is a coNP-complete problem. In this paper, we obtain -time and -time algorithms to decide well coveredness, improving results of Boria et. al. (2015). Moreover, using crown decomposition, we show that such problems admit kernels having linear number of vertices. In 2018, Alves et. al. (2018) proved that recognizing well covered graphs is coW[2]-hard when the independence number is the parameter. Contrasting with such coW[2]-hardness, we present an FPT algorithm to decide well coveredness when and the degeneracy of the input graph are aggregate parameters. Finally, we use the primeval decomposition technique to obtain a linear time algorithm for extended -laden graphs and -graphs, which is FPT parameterized by , improving results of Klein et al (2013).
Keren Censor-Hillel, Dean Leitersdorf, Elia Turner
2018-02-13
We multiply two
matrices over semirings in the Congested Clique model, where fully connected nodes communicate synchronously using -bit messages, within rounds of communication, where denotes the number of non-zero elements in a matrix . By leveraging the sparsity of the input matrices, our algorithm greatly reduces communication compared with general algorithms [Censor-Hillel et al., PODC 2015], improving upon the state-of-the-art for matrices with non-zero elements. Our algorithm exhibits the additional strength of surpassing previous solutions also when only one matrix is sparse. This allows efficiently raising a sparse matrix to a power greater than 2. As applications, we speed up 4-cycle counting and APSP in sparse graphs. Our algorithmic contribution is a new \emph{deterministic} method of restructuring the input matrices in a sparsity-aware manner, which assigns each node with element-wise multiplication tasks that are not necessarily consecutive but are balanced, yielding communication-efficient multiplication. Moreover, this new deterministic method for restructuring matrices may be used to restructure the adjacency matrix of input graphs, enabling faster solutions for graph related problems. As an example, we present a new deterministic algorithm which solves the triangle listing problem in rounds, a complexity that was previously obtained by a \emph{randomized} algorithm [Pandurangan et al., SPAA 2018] and matches the lower bound of when of [Izumi and Le Gall, PODC 2017, Pandurangan et al., SPAA 2018]. Our triangle listing algorithm implies triangle counting with the same complexity of rounds, which is a \emph{cubic} improvement over the previous -round algorithm [Dolev et al., DISC 2012].
Vincent Cohen-Addad, Éric Colin de Verdière, Daniel Marx, Arnaud de Mesmay
2019-03-20
We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cut graph of a graph
embedded on a surface is a subgraph of whose removal from leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus has a cut graph of length at most a given value. We prove a time lower bound for this problem of conditionally to ETH. In other words, the first -time algorithm by Erickson and Har-Peled [SoCG 2002, Discr.\ Comput.\ Geom.\ 2004] is essentially optimal. We also prove that the problem is W[1]-hard when parameterized by the genus, answering a 17-year old question of these authors. A multiway cut of an undirected graph with distinguished vertices, called terminals, is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of , conditionally to ETH, for any choice of the genus of the graph and the number of terminals . In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case). Reductions to planar problems usually involve a grid-like structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value of the genus.
Santosh S. Vempala, Andre Wibisono
2019-03-20
We prove a convergence guarantee on the unadjusted Langevin algorithm for sampling assuming only that the target distribution
satisfies a log-Sobolev inequality and the Hessian of is bounded. In particular, is not required to be convex or have higher derivatives bounded.
Laszlo Csirmaz
2018-08-06
Benson's outer approximation algorithm and its variants are the most frequently used methods for solving linear multiobjective optimization problems. These algorithms have two intertwined components: one-dimensional linear optimization one one hand, and a combinatorial part closely related to vertex numeration on the other. Their separation provides a deeper insight into Benson's algorithm, and points toward a dual approach. Two skeletal algorithms are defined which focus on the combinatorial part. Using different single-objective optimization problems - called oracle calls - yield different algorithms, such as a sequential convex hull algorithm, another version of Benson's algorithm with the theoretically best possible iteration count, the dual algorithm of Ehrgott, L"ohne and Shao, and the new algorithm. The new algorithm has several advantages. First, the corresponding one-dimensional optimization problem uses the original constraints without adding any extra variables or constraints. Second, its iteration count meets the theoretically best possible one. As a dual algorithm, it is sequential: in each iteration it produces an extremal solution, thus can be aborted when a satisfactory solution is found. The Pareto front can be "probed" or "scanned" from several directions at any moment without adversely affecting the efficiency. Finally, it is well suited to handle highly degenerate problems where there are many linear dependencies among the constraints. On problems with ten or more objectives the implementation shows a significant increase in efficiency compared to Bensolve - due to the reduced number of iterations and the improved combinatorial handling.
