Shuchi Chawla
Thesis Title:
Graph Algorithms for Planning and Partitioning
Degree Type:
Ph.D. in Computer Science
Advisor(s):
Avrim Blum
Graduated:
December
2005
Abstract:
In this thesis, we present new approximation algorithms as well as hardness of approximation results for 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:
Avrim Blum (Chair)
Anupam Gupta
R. Ravi
Moses Charikar (Princeton University)
Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science
Keywords: Approximation algorithms, combinatorial optimization, robot navigation, vehicle routing, graph partitioning, hardness of approximation
CMU-CS-05-184.pdf (819.56 KB) ( 143 pages)Copyright Notice