05916755

j

05916755 Nagarajan, Viswanath Ravi, R. The directed orienteering problem. Algorithmica 60, No. 4, 1017-1030 (2011). 2011 Springer-Verlag New York Inc., New York EN vehicle routing directed graphs approximation algorithms TSP Zbl 1137.90687

doi:10.1007/s00453-011-9509-2

Summary: 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 \in V$ and a target $k \leq |V|$, compute the minimum length tour that contains $r$ and at least $k$ other vertices. We present a polynomial time $O(\frac{\log^{2} n}{\log\log n}\cdot\log k)$-approximation algorithm for this problem. We use this algorithm for directed $k$-TSP to obtain an $O(\frac{\log^{2} n}{\log\log n})$-approximation algorithm for the directed orienteering problem. This answers positively, the question of poly-logarithmic approximability of directed orienteering, an open problem from [{\it A. Blum} et al. SIAM J. Comput. 37, No. 2, 653--670 (2007; Zbl 1137.90687)]. 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. Using the algorithm for directed orienteering within the framework of Blum et al. [loc.\,cit.] and {\it N. Bansal} et al. [``Approximation algorithms for deadline-TSP and vehicle routing with time windows'', in: ACM Symposium on Theory of Computing, 166--174 (2004)], we also obtain poly-logarithmic approximation algorithms for the directed versions of discounted-reward TSP and vehicle routing problem with time-windows.