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.
Anupam Gupta (Chair)
Nikhil Bansal (Eindhoven University of Technology)