Computer Science Department
School of Computer Science, Carnegie Mellon University


Graph Algorithms for Planning and Partitioning

Shuchi Chawla

September 2005

Ph.D. Thesis

Keywords: Approximation algorithms, combinatorial optimization, robot navigation, vehicle routing, graph partitioning, hardness of approximation

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.

143 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by