Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Approximate All-Pairs Shortest Paths: Recent Advances and Open Questions
event speaker icon
Michal Dory (Haifa university)
event date icon
Wednesday, 14.06.2023, 12:30
event location icon
Taub 201
The All-Pairs Shortest Paths (APSP) problem is one of the most fundamental problems in graph algorithms. It is well-known that APSP can be solved in O(n^3) time in weighted graphs, and in O(n^{omega}) time in unweighted graphs, where omega<2.376 is the exponent of matrix multiplication. However, these complexities may be high for large graphs, and it is desirable to find faster algorithms. One approach for obtaining faster algorithms is to compute approximations for APSP, rather than computing the distances exactly. In this talk, I will give an overview of algorithms for approximate APSP, and discuss recent progress and interesting open questions in this area. The talk will overview some classic results based on [Aingworth, Chekuri, Indyk, and Motwani, 1999] and [Dor, Halperin and Zwick, 2000] as well as recent results based on a joint work with Sebastian Forster, Yasamin Nazari and Tijn de Vos.