English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max

MPS-Authors
/persons/resource/persons44182

Bringmann,  Karl
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44857

Künnemann,  Marvin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

arXiv:1907.11078.pdf
(Preprint), 481KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Bringmann, K., Künnemann, M., & Węgrzycki, K. (2019). Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max. Retrieved from http://arxiv.org/abs/1907.11078.


Cite as: http://hdl.handle.net/21.11116/0000-0005-3D73-6
Abstract
Zwick's $(1+\varepsilon)$-approximation algorithm for the All Pairs Shortest Path (APSP) problem runs in time $\widetilde{O}(\frac{n^\omega}{\varepsilon} \log{W})$, where $\omega \le 2.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 $\log W$ 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^\omega}{\varepsilon} \text{polylog}(\frac{n}{\varepsilon}))$ 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^{\frac{\omega + 3}{2}} \varepsilon^{-1} \text{polylog}(\frac{n}{\varepsilon}))$. 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 $\frac{\omega + 3}{2}$ 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.