Title: Real-weighted shortest paths beyond dynamic programming
Abstract: The textbook algorithm for single-source shortest paths with real-valued edge weights runs in $O(mn)$ time on a graph with $m$ edges and $n$ vertices. A recent breakthrough algorithm by Fineman takes $\tilde{O}(m n^{8/9})$ randomized time. We present an $\tilde{O}(m n^{4/5})$ randomized time algorithm building on ideas from that work. The talk will aim to present both Fineman’s algorithms and our modifications to improve it. Joint work with Yufan Huang and Peter Jin.
Bio: Kent Quanrud is an Assistant Professor in the Computer Science department at Purdue University. He received his PhD from UIUC in 2018, and has been at Purdue since. He is broadly interested in theoretical science, algorithms, and combinatorial optimization. Recent research interests include basic graph problems such as directed cut, densest subgraph, and shortest paths; as well as developing randomized and algorithmic techniques for problems involving matroids and submodular functions.
