The Directed Orienteering Problem |
| |
Authors: | Viswanath Nagarajan R Ravi |
| |
Affiliation: | (1) 84081 Baronissi, Salerno, (SA), Italy;(2) Dip. Mat. e Inform., Univ. Salerno, 32611 Gainesville, FL, USA;(3) Center for Applied Optim. Dept. Industrial and Systems Engin., Univ. Florida, 32611 Gainesville, FL, USA;(4) Information Sci. Res. AT&T Labs Res., Florham Park, Florham Park, 07932, NJ, USA |
| |
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(\fraclog2 nloglogn·logk)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(\fraclog2 nloglogn)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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|