Better Approximation Algorithms for Graph Diameter

The diameter is a fundamental graph parameter and its computation is necessary in many applications. The fastest known way to compute the diameter exactly is to solve the All-Pairs Shortest Paths (APSP) problem. In the absence of fast algorithms, attempts were made to seek fast algorithms that approximate the diameter.
This work continues this line of research and shows new algorithms for approximating the diameter of weighted directed graphs as well as computing vertex eccentricities. We also show improved results for both cases of additive and multiplicative approximation.

This is joint work with Shiri Chechik, Daniel H. Larkin, Liam Roditty, Robert E. Tarjan, and Virginia Vassilevska Williams.
Grant Schoenebeck is an Assistant Professor of Computer Science and Engineering at the University of Michigan. Dr. Schoenebeck studies how computational approaches and insights can help us to better understand the world we live in. His research interests span several fields of theoretical computer science including computational complexity theory and topics intersecting theoretical computer science and social and economic networks.

Before coming to the University of Michigan, he was the Simons Foundation Postdoctoral Fellow in Theoretical Computer Science at Princeton University, the Senior Postdoctoral Fellow at the Center for Computational Intractability, and a visitor at the Institute for Advanced Study. He received his PhD in computer science from UC Berkeley.