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

Download file# Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems

journal contribution

posted on 11.05.2010, 00:00 by Viswanath Nagarajan, Ramamoorthi RaviRamamoorthi RaviThis 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(log

^{2}n·logk)-approximation algorithm for this problem. We use this algorithm for directed k-TSP to obtain an O(log^{2}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(log^{2}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.