Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max

DOI10.1145/3313276.3316373MaRDI QIDQ5212835zbMATH OpenOpenAlexWikidataFDO

Authors Karl Bringmann, Marvin Künnemann, Karol Węgrzycki

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.11078

zbMATH Keywords

approximation schemesfine-grained complexityhardness of approximationstrongly polynomial algorithms

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: Zwick's $(1+varepsilon)$-approximation algorithm for the All Pairs Shortest Path (APSP) problem runs in time $widetildeO(frac{n}^{o}megavarepsilonlogW)$, where $omegale2.373$ is the exponent of matrix multiplication and $W$ denotes the largest weight. This can be used to approximate several graph characteristics including the diameter, radius, median, minimum-weight triangle, and minimum-weight cycle in the same time bound. Since Zwick's algorithm uses the scaling technique, it has a factor $logW$ in the running time. In this paper, we study whether APSP and related problems admit approximation schemes avoiding the scaling technique. That is, the number of arithmetic operations should be independent of $W$; this is called strongly polynomial. Our main results are as follows. - We design approximation schemes in strongly polynomial time $O(frac{n}^{o}megavarepsilonextpolylog(fracnvarepsilon))$ for APSP on undirected graphs as well as for the graph characteristics diameter, radius, median, minimum-weight triangle, and minimum-weight cycle on directed or undirected graphs. - For APSP on directed graphs we design an approximation scheme in strongly polynomial time $O(n^{fracomega+32}varepsilo{n}^{-1}extpolylog(fracnvarepsilon))$. This is significantly faster than the best exact algorithm. - We explain why our approximation scheme for APSP on directed graphs has a worse exponent than $omega$: Any improvement over our exponent $fracomega+32$ would improve the best known algorithm for Min-Max Product In fact, we prove that approximating directed APSP and exactly computing the Min-Max Product are equivalent.

Recommendations

• Approximate shortest paths in weighted graphs
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• From circuit complexity to faster all-pairs shortest paths
• Faster all-pairs shortest paths via circuit complexity
• All-pairs shortest paths with a sublinear additive error

Cited in

(6)

• Computing generalized convolutions faster than brute force
• Computing generalized convolutions faster than brute force
• Approximate min-sum subset convolution
• Algorithms, reductions and equivalences for small weight variants of all-pairs shortest paths
• Fully dynamic algorithms for minimum weight cycle and related problems
• Additive, near-additive, and multiplicative approximations for APSP in weighted undirected graphs: trade-offs and algorithms

This page was built for publication: Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212835)