@article{Böckenhauer_Forlizzi_Hromkovic_Kneis_Kupke_Proietti_Widmayer_2007, title={On the Approximability of TSP on Local Modifications of Optimally Solved Instances}, volume={2}, url={https://journals.lib.unb.ca/index.php/AOR/article/view/2803}, abstractNote={Given an instance of TSP together with an optimal solution, we consider the scenario in which this instance is modified locally, where a local modification consists in the alteration of the weight of a single edge. More generally, for a problem <em>U</em>, let LM-<em>U</em> (local-modification-<em>U</em>) denote the same problem as <em>U</em>, but in LM-<em>U</em>, we are also given an optimal solution to an instance from which the input instance can be derived by a local modification. The question is how to exploit this additional knowledge, i.e., how to devise better algorithms for LM-<em>U</em> than for <em>U</em>. Note that this need not be possible in all cases: The general problem of LM-TSP 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 &#x03B2;-triangle inequality (LM-&#x0394;<sub>&#x03B2;</sub>-TSP) remains NP-hard for all &#x03B2;&gt;&#189;. However, for LM-&#x0394;-TSP (i.e., metric LM-TSP), we will present an efficient 1.4-approximation algorithm. In other words, the additional information enables us to do better than if we simply used Christofides’ algorithm for the modified input. Similarly, for all 1&lt;&#x03B2;&lt;3.34899, we achieve a better approximation ratio for LM-&#x0394;-TSP than for &#x0394;<sub>&#x03B2;</sub>-TSP. For &#189;&#x2264;&#x03B2;&lt;1, we show how to obtain an approximation ratio arbitrarily close to 1, for sufficiently large input graphs.}, number={2}, journal={Algorithmic Operations Research}, author={Böckenhauer, Hans-Joachim and Forlizzi, Luca and Hromkovic, Juraj and Kneis, Joachim and Kupke, Joachim and Proietti, Guido and Widmayer, Peter}, year={2007}, month={Sep.}, pages={83} }