All Pairs Shortest Path in Quadratic Time with High Probability
- Benjamin Sudakov
All-pairs shortest path problem is one of the most important, and most studied algorithmic graph problems. For this problem many researches develop algorithms which work well on random instances, most notably complete directed graphs on n vertices with random weights on their edges. The simplest such model, on which we focus in this talk, is the one in which all edge weights are drawn independently at random from the uniform distribution on [0,1]
We present an all-pairs shortest path algorithm in this setting whose running time is O(n2), in expectation and with high probability. This is clearly best possible and resolves a long standing open problem.
Joint work with Y. Peres, D. Sotnikov and U. Zwick
Speaker Details
Benny Sudakov got his Ph.D from Tel Aviv University in 1999 under Noga Alon, had appointments in Princeton University and Institute for Advanced Studies and is currently professor of mathematics in UCLA. He is the recipient of an Alfred P. Sloan Foundation Fellowship, an NSF CAREER Award and was invited speaker at 2010 International Congress of Mathematicians. His main interests are Combinatorics and its applications in Computer Science
-
-
Jeff Running
-
-
Watch Next
-
-
-
-
VoluMe: Authentic 3D Video Calls from Live Gaussian Splat Prediction
- Antonio Criminisi,
- Charlie Hewitt,
- Marek Kowalski (HE/HIM)
-
GenAI for Supply Chain Management: Present and Future
- Georg Glantschnig,
- Beibin Li,
- Konstantina Mellou
-
Using Optimization and LLMs to Enhance Cloud Supply Chain Operations
- Beibin Li,
- Konstantina Mellou,
- Ishai Menache
-
-
-
-