Computer Science Thesis Proposal

Tuesday, November 21, 2017 - 10:30am


8102 Gates Hillman Centers



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, Contact:


Thesis Proposal