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