About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Algorithmica (New York)
Paper
The directed orienteering problem
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 2n/log log n. logk) -approximation algorithm for this problem. We use this algorithm for directed k-TSP to obtain an O(log 2n/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 Blum et al. (SIAM J. Comput. 37(2):653-670, 2007). 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 and Pal in IEEE Symposium on Foundations in Computer Science, pp. 245-253, 2005). Using the algorithm for directed orienteering within the framework of Blum et al. (SIAM J. Comput. 37(2):653-670, 2007) and Bansal et al. (ACM Symposium on Theory of Computing, pp. 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. © 2011 Springer Science+Business Media, LLC.