Poly-logarithmic Approximation Algorithms for Directed Vehicle Ro.pdf.pdf' (216.19 kB)

Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems

Download (216.19 kB)
journal contribution
posted on 11.05.2010 by Viswanath Nagarajan, Ramamoorthi 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.