Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems
journal contributionposted 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.. 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 ). Using the algorithm for directed orienteering within the framework of Blum et al. and Bansal et al., we also obtain poly-logarithmic approximation algorithms for the directed versions of discounted-reward TSP and the vehicle routing problem with time-windows.