Theory Seminar

Better Approximation Algorithms for Graph Diameter

Grant Schoenebeck

Assistant Professor
University of Michigan
Friday, October 11, 2013
10:30am - 11:30am
3941 Beyster Bldg.

Add to Google Calendar

About the Event

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.

Additional Information

Contact: Grant Schoenebeck

Sponsor(s): CSE

Open to: Public

Web Page: http://web.eecs.umich.edu/~schoeneb/index.html