Shuchi Chawla

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