Theory Seminar, Wednesday April 29: Ariel Sapir (BIU) - Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms

[Arnold Filtser]

Hi all,

We are happy to resume our theory seminar in the spring semester. The first lecture will take place next week (Wed April 29, at 12), where our very own Ariel Sapir will tell us about APSP approximations.

Location: Building 503 room 226.

Looking forward to seeing you all there,

Arnold

https://theory.cs.biu.ac.il/

Speaker: Ariel Sapir (BIU)
Title: Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
Abstract: We recall the problem of All-Pairs Shortest Path (APSP). The APSP conjecture states there exists no \varepsilon>0 s.t. APSP can be computed in \tilde O(n^{3-\varepsilon}. To overcome this, the problem of All-Pairs Approximate Shortest Paths (APASP) has been studied for nearly three decades. A seminal work by Dor, Halperin and Zwick [FOCS'96, SICOMP'00] presented two algorithms for an additive +2(k+1)-APASP, one with n^{2-\frac{1}{k+2}} m^{\frac{1}{k+2}} runtime and another with n^{2+\frac{1}{3k+2}} runtime. We discuss a commensurate weighted version of the problem, namely: additive +2\sum_{i=1}^{k+1} W_i-APASP, where W_i is the weight of the i^th heaviest edge on a shortest path between two vertices, and show that both problems can be solved in the same runtime. We also consider a near-additive (1+\varepsilon, \min{2W_{1},4W_{2}})-APASP and a family of multiplicative  (\frac{3\ell+4}{\ell+2}+\varepsilon)-APASP (e.g. 2+\varepsilon, 7/3+\varepsilon, 5/2+\varepsilon...). Finally, we "bypass" an \tilde \Omega (n^{\omega}) conditional lower bound by Dor, Halperin, and Zwick for \alpha-APASP with \alpha<2, by allowing an additive term (e.g. (\frac{6k+3}{3k+2},\sum_{i=1}^{k+1} W_i)-APASP in n^{2+\frac{1}{3k+2}} runtime).

[Arnold Filtser]

The seminar starts in one hour!