hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC
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.
