简介: |
Short Bio:
Uri Zwick received his B.Sc. degree in Computer Science from the Technion, Israel Institute of Technology, and his M.Sc. and Ph.D. degrees in Computer Science from Tel Aviv University. He is currently a Professor of Computer Science in Tel Aviv University. His main research interests are: algorithms and complexity, combinatorial optimization, mathematical games, and recreational mathematics.
Abstract:
We present an All-Pairs Shortest Paths (APSP) algorithm whose expected running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0, 1] is O(n^2). This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the expected number of locally shortest paths in such randomly weighted graphs is O(n^2). We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O(log^2 n) expected time.
Joint work with Yuval Peres, Benny Sudakov and Uri Zwick |
