The Directed Orienteering Problem
The Directed Orienteering Problem
复制标题
定向定向问题
作者：
V. Nagarajan;R. Ravi
本文研究了非对称度量下的车辆路径问题。我们的出发点是有向k-TSP问题：给定一个非对称度量(V，d)，一个根r∈V和一个目标k≤|V|，计算包含r和至少k个其他顶点的最小长度环路。对于这个问题，我们给出了一个多项式时间$O(frc{log^{2}n}{loglogn}cdotlogk)$-近似算法。利用有向k-TSP的这个算法，我们得到了有向定向问题的$O(Frc{log^{2}n}{loglogn})$-近似算法。这肯定地回答了定向定向运动的多对数逼近问题，这是Blum等人提出的一个公开问题。(暹罗J.康普特)37(2)：653-670,2007)。以前最著名的结果是准多项式时间算法，对于有向k-TSP，具有O(对数 2k)的近似保证，对于有向定向，具有O(对数 n)的近似保证(切库里和帕尔在IEEE计算机科学基础研讨会上，第2245-253页，2005年)。在Blum等人的框架内使用定向定向的算法。(暹罗J.康普特)37(2)：653-670,2007)和Bansal等人。(ACM计算理论研讨会，第166-174页，2004)，我们还得到了有向形式的折扣奖励TSP和带时间窗的车辆路径问题的多对数近似算法。
This paper studies vehicle routing problems on asymmetric metrics. Our starting point is the directedk-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(frac{log^{2} n}{loglog n}cdotlog k)$-approximation algorithm for this problem. We use this algorithm for directed k-TSP to obtain an $O(frac{log^{2} n}{loglog 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 2k) 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.