![](https://csd.cmu.edu/sites/default/files/styles/full_width_focal_point/public/graduate.png.webp?itok=Wsy3nMEH)
Michael Dinitz
Algorithms and Models for Problems in Networking
Degree Type:
Ph.D. in Computer Science
Advisor(s):
Anupam Gupta
Graduated:
August
2010
Abstract:
Many interesting theoretical problems arise from computer networks. In this thesis we will consider three of them: algorithms and data structures for problems involving distances in networks (in particular compact routing schemes, distance labels, and distance oracles), algorithms for wireless capacity and scheduling problems, and algorithms for optimizing iBGP overlays in autonomous systems on the Internet. While at first glance these problems may seem extremely different, they are similar in that they all attempt to look at a previously studied networking problem in new, more realistic frameworks. In other words, they are all as much about new models for old problems as they are about new algorithms. In this thesis we will define these models, design algorithms for them, and prove hardness and impossibility results for these three types of problems.
Thesis Committee:
Anupam Gupta (Chair)
Avrim Blum
Bruce Maggs
Matthew Andrews
Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science
Keywords: Algorithms, networking, spanners, routing, wireless, capacity, BGP
CMU-CS-10-136.pdf (914.17 KB) ( 105 pages)Copyright Notice