Approximating APSP without Scaling

We study whether the factor log W can be avoided, that is, whether APSP and related problems admit "strongly polynomial" approximation schemes, whose running time is independent of W. For APSP on undirected graph as well as for several graph characteristics on directed or undirected graphs we remove the log W-factor from Zwick's running time. For APSP on directed graphs, we design a strongly polynomial approximation scheme in time O(n^{(omega + 3)/2} / eps). We also explain why this has a worse exponent than omega: Any improvement over our exponent (omega + 3)/2 would improve the best known algorithm for MinMaxProduct. In fact, we prove that approximating directed APSP and exactly computing the MinMaxProduct are equivalent.

Joint work with Marvin Künnemann and Karol Wegrzycki.