Computer Science Thesis Oral

Friday, August 31, 2018 - 3:00pm to 4:00pm

Location:

8102 Gates Hillman Centers

Speaker:

GURU PRASHANTH GURUGANESH , Ph.D. Student https://www.csd.cs.cmu.edu/people/graduate-student/guru-guruganesh

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 independent 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 (Centrum Wiskunde & Informatica / Eindhoven University of Technology)

For More Information, Contact:

Keywords:

Thesis Oral