Recent Progress on Approximate APSP

Speaker(s)

Karol Węgrzycki

Affiliation

MIMUW

Date

June 19, 2019, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

In this talk we prove the equivalence of computing the approximate (min,+)-product
of two $n \times n$ matrices with arbitrary values and (min,max)-product. This
yields a first subcubic strongly polynomial approximation for the all-pairs
shortest path problem (APSP). The algorithm runs in time $O(n^\frac{\omega
+ 3}{2} \eps^{-1} \text{polylog}(n,\eps)) \le O(\frac{n^{2.69}}{\eps})$ on
word RAM. In comparison, a scaling-based approximation scheme for APSP runs
in $O(\frac{n^\omega}{\eps} \log{W})$ time (where $W$ is the upper bound
on the weight) and is not strongly polynomial. 

The result is rather unexpected. For applications of APSP (i.e., diameter,
radius, minimum weight cycle, etc.) we show that the
known algorithms can be transformed into a strongly polynomial relatively
easily. Additionally, for undirected APSP we show that contracting edges and
amortized analysis also give the power to obtain a $\Ot(n^\omega/\eps)$
strongly polynomial time. However, for APSP we cannot do such operations.
In fact, this makes sense, as we prove that approximate APSP is at least as
hard as exact (min,max)-product for which no $O(n^\omega)$ algorithm is known.

Joint work with Karl Bringmann and Marvin K\"unnemann (MPI Saarbr\"ucken).

---