Poly-logarithmic approximation algorithms for Directed Vehicle Routing Problems

Abstract. 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(log 2 n · log k)-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(log n) 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.