Not All Insertion Methods Yield Constant Approximate Tours in the Euclidean Plane
Not All Insertion Methods Yield Constant Approximate Tours in the Euclidean Plane
复制标题
并非所有插入方法都会在欧几里得平面上产生恒定的近似游览
DOI：
10.1016/0304-3975(94)90257-7
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
K. Pruhs
中科院分区：
文献类型：
--
作者：
V. Bafna;B. Kalyanasundaram;K. Pruhs
旅行商问题的一种插入启发式算法迭代地将城市添加到现有的旅行中，方法是以最便宜的方式将通过新城市的两条边路径替换为一条边。Rosenkrantz(1977)问道，是否每个顶点的插入顺序都给出了一个恒定因子近似算法。我们通过证明对于某些点集，存在一个序，它产生长度为Ω(logn，⧸，logn)倍最优的环游，即使其下的度量空间是欧几里得平面。
An insertion heuristic for the traveling salesman problem adds cities iteratively to an existing tour by replacing one edge with a two-edge path through the new city in the cheapest possible way. Rosenkrantz (1977) asked whether every order of inserting vertices gives a constant-factor approximation algorithm. We answer this question by showing that for some point sets, there is an order that yields tours with length Ω (log n⧸ log log n) times optimum, even if the underlying metric space is the Euclidean plane.