Computer Science Thesis Proposal

  • Ph.D. Student
  • Computer Science Department
  • Carnegie Mellon University
Thesis Proposals

Topics in Approximation and Online Algorithms

Approximation Algorithms, and its sister field Online Algorithms have had a pro- found impact in theoretical computer science. Questions in this field have created a host of new algorithmic tools and techniques that have had impact in the other fields such as operations research, machine learning and complexity theory. In this thesis, we study several problems and propose new variations on them. We achieve new results on classical problems such as finding indpendent sets in degree-d graphs and fraction- ally sub-additive network design problem. We also look at several new problems such as aversion k-clustering, online matroid intersection and fully dynamic bin packing with recourse.

Thesis Committee:
Anupam Gupta (Chair)
R. Ravi
Bernhard Haeupler
Nikhil Bansal (Eindhoven University of Technology)

Copy of Thesis Summary

For More Information, Please Contact: