CS 789 THEORY SEMINAR [home]

Speaker:    Shuchi Chawla
Affiliation:  CMU
Date:    April 12, 2004     
Title:    Approximation Algorithms for Path-Planning Problems     

Abstract:

Given a weighted graph with values on vertices and a length bound D, we consider the problem of constructing a rooted path of length at most D that visits as many vertices in the graph as possible. This problem is traditionally known as "Orienteering". Path-planning problems such as Orienteering arise in a variety of fields such as robot navigation, manufacturing and production planning. Until recently, no approximation algorithm was known for this problem on general graphs. In this talk, we give a 3-approximation for the Orienteering problem. We also consider a generalization of this problem -- the Time-Window problem -- where every vertex in the graph has a time-window associated with it and the goal is to maximize the number of nodes visited within their time-windows. We give an O(log^2 n)-approximation for the Time-Window problem.

This is joint work with Nikhil Bansal, Avrim Blum and Adam Meyerson.