Shuchi Chawla
Computer Science Department
Date: June 22
Time: 1:30 PM
Place: Wean 5409
Title: Graph Algorithms for Planning and Partitioning
Thesis abstract:
In this thesis, we study the approximability of several planning and partitioning problems. In planning problems, one is typically given a set of locations to visit, along with timing constraints, such as deadlines for visiting them; The goal is to visit a large number of locations as efficiently as possible. We give the first approximation algorithms for problems such as Orienteering, Deadlines-TSP, and Time-Windows-TSP, as well as results for planning in stochastic graphs (Markov decision processes). The goal in partitioning problems is to partition a set of objects into clusters while satisfying “split” or “combine” constraints on pairs of objects. We consider three kinds of partitioning problems, viz. Correlation Clustering, Sparsest Cut, and Multicut. We give approximation algorithms for the first two, and improved hardness of approximation results for Sparsest Cut and Multicut.
Thesis committee members:
Avrim Blum
Anupam Gupta
R. Ravi
Moses Charikar, Princeton University
Thesis summary available at http://www.cs.cmu.edu/~shuchi/thesis/
