Carnegie Mellon University
Poly-logarithmic Approximation Algorithms for Directed Vehicle Ro.pdf.pdf' (216.19 kB)
Download file

Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems

Download (216.19 kB)
journal contribution
posted on 2010-05-11, 00:00 authored by Viswanath Nagarajan, Ramamoorthi RaviRamamoorthi Ravi
This paper studies vehicle routing problems on asymmetric metrics. Our starting point is the directed k -TSP problem: given an asymmetric metric (V,d), a root r ∈ V and a target k ≤ |V|, compute the minimum length tour that contains r and at least k other vertices. We present a polynomial time O(log2 n·logk)-approximation algorithm for this problem. We use this algorithm for directed k-TSP to obtain an O(log2 n)-approximation algorithm for the directed orienteering problem. This answers positively, the question of poly-logarithmic approximability of directed orienteering, an open problem from Blum et al.[2]. The previously best known results were quasi-polynomial time algorithms with approximation guarantees of O(log2 k) for directed k-TSP, and O(logn) for directed orienteering (Chekuri & Pal [4]). Using the algorithm for directed orienteering within the framework of Blum et al.[2] and Bansal et al.[1], we also obtain poly-logarithmic approximation algorithms for the directed versions of discounted-reward TSP and the vehicle routing problem with time-windows.




Usage metrics