Results 2371 - 2380 of 23908

I present a nearly linear work parallel algorithm for approximating the Held-Karp bound for the Metric TSP problem. Given an edge-weighted undirected graph G=(V,E) on m edges and ϵ>0, it returns a (1+ϵ)-approximation to the Held-Karp bound with high probability, in Õ (m/(ϵ^4)) work and Õ (1/(ϵ^4)) depth. While a nearly linear time sequential algorithm was known for almost a decade (Chekuri and Quanrud'17), it was not known how to simultaneously achieve nearly linear work alongside polylogarithmic depth. Using a reduction by Chalermsook et al.'22, we also give a parallel algorithm for computing a (1+ϵ)-approximate fractional solution to the k-edge-connected spanning subgraph (kECSS) problem, with the same complexity. To obtain these results, we introduce a notion of core-sequences for the parallel Multiplicative Weights Update (MWU) framework (Luby-Nisan'93, Young'01). For the Metric TSP and kECSS problems, core-sequences enable us to exploit the structure of approximate minimum cuts to reduce the cost per iteration and/or the number of iterations. The acceleration technique via core-sequences is generic and of independent interest. In particular, it improves the best-known iteration complexity of MWU algorithms for packing/covering LPs from poly(lognnz(A)) to polylogarithmic in the product of cardinalities of the core-sequence sets where A is the constraint matrix of the LP. For certain implicitly defined LPs such as the kECSS LP, this yields an exponential improvement in depth.

While spectral sparsification is well understood for undirected graphs, developing efficient algorithms for spectral sparsification of Eulerian (directed) graphs has been challenging. We present a new framework for sparsifying Eulerian graphs that utilizes electrical routings to preserve Eulerianness, and exploits a simple effective resistance partitioning for improved sparsifier quality. Our approach yields state-of-the-art algorithms for constructing Eulerian sparsifiers, both in terms of running time and the resulting sparsity. As a consequence, we obtain significantly faster algorithms for solving directed Laplacian systems and computing stationary distributions of markov chains. This is joint work with Arun Jambulapati, Aaron Sidford, Kevin Tian, and Yibin Zhao.

We study the fully-dynamic all-pair shortest paths (APSP) problem on planar graphs: given an n−vertex planar graph G=(V, E) undergoing edge insertions and deletions, the goal is to efficiently process these updates and support distance and shortest path queries. We give a (1+ϵ)−approximate dynamic algorithm that supports edge updates and distance queries in n^{o(1)} time, for any 1/poly(logn) < ϵ < 1. Our result is a significant improvement over the best previously known bound of ~O(\sqrt{n}) on update and query time due to [Abraham, Chechik, and Gavoille, STOC ’12], and bypasses a Ω(\sqrt{n}) conditional lower-bound on update and query time for exact fully dynamic planar APSP [Abboud and Dahlgaard, FOCS ’16]. The main technical contribution behind our result is to dynamize the planar emulator construction due to [Chang, Krauthgamer, Tan, STOC ’22].