Computer Science Student Defense: Zeyu Zhang, Johns Hopkins University – “Approximation Algorithms and Hardnesses for Compressing Graphs with Distance Constraints”

March 15, 2019 @ 2:00 pm – 4:00 pm


Malone 107


Graphs have been widely utilized in network design and other applications. A natural question is, can we keep as few edges of the original graph as possible, but still make sure that the vertices are connected within certain distance constraints.

In this thesis, we will consider different versions of graph compression problems, including graph spanners, approximate distance oracles, and Steiner networks. Since these problems are all $mathrm{NP}$-hard problems, we will mostly focus on designing approximation algorithms and proving inapproximability results.


I am a Ph.D. candidate advised by Professor Michael Dinitz in the Department of Computer Science at Johns Hopkins University. My research focuses on approximation algorithms and graph algorithms. I received a B.S. in Mathematics from Tsinghua University in 2014.


Michael Dinitz

Back to top