Reusing Optimal TSP Solutions for Locally Modified Input Instances
Reusing Optimal TSP Solutions for Locally Modified Input Instances
复制标题
为本地修改的输入实例重用最佳 TSP 解决方案
DOI：
10.1007/978-0-387-34735-6_21
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
P. Widmayer
中科院分区：
文献类型：
--
作者：
Hans;L. Forlizzi;J. Hromkovic;Joachim Kneis;Joachim Kupke;Guido Proietti;P. Widmayer
给定一个优化问题的实例以及最优解，我们考虑局部修改该实例的情况。在图形问题中，例如，可以去除或添加奇异边，或者可以改变边权重，等等。对于问题U和这样的局部修改操作，令LM-U（local-modification-U）表示结果问题。问题是是否有可能利用原始实例的最佳解决方案的额外知识，即，LM-U在计算上是否比U更易处理。在这里，我们给出了非平凡的例子，这两个问题，这是和问题的情况下，这不是。我们的主要结果如下：
1.
通过改变奇异边的代价的局部修正，将旅行商问题（TSP）转化为与TSP本身一样难的LM-TSP问题，即，除非P=NP，否则对于任何多项式p，LM-TSP都没有多项式时间p（n）-近似算法。此外，对于所有β > 1/2，输入必须满足β三角不等式的LM-TSP（LM-Δ β -TSP）仍然是NP-难的。
2.
对于LM-Δ-TSP（即，度量LM-TSP），提出了一种有效的1.4-近似算法。换句话说，额外的信息使我们能够做得比我们简单地使用Christofides的算法来修改输入更好。
3.
类似地，对于所有1 < β < 3.34899，我们实现了LM-Δ β -TSP比α ′-TSP更好的近似比。
4.
度量TSP的最后期限（时间窗口），如果一个单一的最后期限或成本的一个单一的边缘被修改，表现出相同的下界的近似性，在这些本地修改的版本，目前已知的原始问题。instance.第二种结构扩大了这一优势。在时间X开始的图尔斯，不同于在时间X+g和X + g之间开始的那些，可能花费一些额外的时间来访问一组顶点，除非提前访问，否则将导致迟来的图尔斯在巨大的距离γ上曲折地运行k次。
Given an instance of an optimization problem together with an optimal solution, we consider the scenario in which this instance is modified locally. In graph problems, e.g., a singular edge might be removed or added, or an edge weight might be varied, etc. For a problem U and such a local modification operation, let LM-U (local-modification-U) denote the resulting problem. The question is whether it is possible to exploit the additional knowledge of an optimal solution to the original instance or not, i.e., whether LM-U is computationally more tractable than U. Here, we give non-trivial examples both of problems where this is and problems where this is not the case. Our main results are these:
1.
The local modification to change the cost of a singular edge turns the traveling salesperson problem (TSP) into a problem LM-TSP which is as hard as TSP itself, i.e., unless P=NP, there is no polynomial-time p(n)-approximation algorithm for LM-TSP for any polynomial p. Moreover, LM-TSP where inputs must satisfy the β triangle inequality (LM-Δ β -TSP) remains NP-hard for all β > 1/2.
2.
For LM-Δ-TSP (i.e., metric LM-TSP), an efficient 1.4-approximation algorithm is presented. In other words, the additional information enables us to do better than if we simply used Christofides’ algorithm for the modified input.
3.
Similarly, for all 1 < β < 3.34899, we achieve a better approximation ratio for LM-Δ β -TSP than for Δ’-TSP.
4.
Metric TSP with deadlines (time windows), if a single deadline or the cost of a single edge is modified, exhibits the same lower bounds on the approximability in these local-modification versions as those currently known for the original problem. instance. A second construction inflates this advantage. Tours which start at time X, different from those that start between times X+g and X +ςg, may spend some extra time to visit a group of vertices which, unless visited early, will cause belated tours to run k times zigzag across a huge distance γ.