Shuchi Chawla

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.