The angular-metric traveling salesman problem
The angular-metric traveling salesman problem
复制标题
角度度量旅行商问题
DOI：
10.1137/s0097539796312721
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
B. Schieber
中科院分区：
文献类型：
--
作者：
A. Aggarwal;D. Coppersmith;S. Khanna;R. Motwani;B. Schieber
在机器人技术中的应用的启发，我们制定的问题，最小化的TSP旅游的一组点在欧几里德空间，其中的角度成本的旅游是在点的方向变化的总和的总角度成本。我们建立了这两个问题的NP-困难的循环覆盖问题和它的放松。然后，我们考虑这些问题的近似算法的设计问题，并表明这两个问题可以近似为一个比率内的O（log n）在多项式时间。我们还考虑了同时逼近TSP巡回赛的角度和长度措施的问题。在研究由此产生的权衡，我们选择专注于两个性能比的总和，并提供严格的界限上的总和。最后，我们考虑了角测度的极值，并得到了它的本质紧界，在这个扩展的抽象中，我们将注意力限制在平面上，但我们的所有结果都很容易推广到高维。
Motivated by applications in robotics, we formulate the problem of minimizing the total angle cost of a TSP tour for a set of points in Euclidean space, where the angle cost of a tour is the sum of the direction changes at the points. We establish the NP-hardness of both this problem and its relaxation to the cycle cover problem. We then consider the issue of designing approximation algorithms for these problems and show that both problems can be approximated to within a ratio of O(log n) in polynomial time. We also consider the problem of simultaneously approximating both the angle and the length measure for a TSP tour. In studying the resulting tradeoff, we choose to focus on the sum of the two performance ratios and provide tight bounds on the sum. Finally, we consider the extremal value of the angle measure and obtain essentially tight bounds for it. In this extended abstract we restrict our attention to the planar setting, but all our results are easily extended to higher dimensions.