Title: The Directed Orienteering Problem
Speaker: Viswanath Nagarajan
When: October 25, 16:30-17:30
Where: Wean Hall 5302
Abstract:
We consider the orienteering problem on asymmetric metrics: given a directed metric (V,d), a starting vertex s, an ending vertex t, and a length bound D, find an s-t path having length at most D that maximizes the number of vertices covered. We give an approximation algorithm for this problem achieving a guarantee of O(log^2 n). The previously best known result was an O(log n)-approximation algorithm that runs in quasi-polynomial time (Chekuri & Pal ‘05). For the undirected special case of this problem, a 3-approximation algorithm was known (Bansal et al. ‘04). Our result answers positively the question of poly-logarithmic approximability of the directed orienteering problem (Blum et al. ‘03). This is joint work with R. Ravi.
