All Pairs Shortest Path in Quadratic Time with High Probability

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

Date:
Speakers:
Benjamin Sudakov