caa a22 4500 445804548 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s00453-011-9509-2 doi (NATIONALLICENCE)springer-10.1007/s00453-011-9509-2 The Directed Orienteering Problem [Elektronische Daten] [Viswanath Nagarajan, R. 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), aroot 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(\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 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. Springer Science+Business Media, LLC, 2011 Vehicle routing nationallicence Directed graphs nationallicence Approximation algorithms nationallicence TSP nationallicence Nagarajan Viswanath IBM T.J. Watson Research Center, 10598, Yorktown Heights, NY, USA aut Ravi R. Tepper School of Business, Carnegie Mellon University, 15213, Pittsburgh, PA, USA aut Algorithmica Springer-Verlag 60/4(2011-08-01), 1017-1030 0178-4617 60:4<1017 2011 60 453 https://doi.org/10.1007/s00453-011-9509-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-011-9509-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Nagarajan Viswanath IBM T.J. Watson Research Center, 10598, Yorktown Heights, NY, USA aut NATIONALLICENCE 700 1- Ravi R. Tepper School of Business, Carnegie Mellon University, 15213, Pittsburgh, PA, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/4(2011-08-01), 1017-1030 0178-4617 60:4<1017 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer