Vol 2 No 2 (2007)

On the Approximability of TSP on Local Modifications of Optimally Solved Instances

Hans-Joachim Böckenhauer
ETH Zurich
Luca Forlizzi
Universita di L'Aquila
Juraj Hromkovic
ETH Zurich
Joachim Kneis
RWTH Aachen
Joachim Kupke
Google Inc.
Guido Proietti
Universita di L'Aquila
Peter Widmayer
ETH Zurich
Published September 2, 2007
  • TSP,
  • reoptimization,
  • approximation algorithms,
  • relaxed triangle inequality,
  • sharpened triangle inequality
How to Cite
Böckenhauer, H.-J., Forlizzi, L., Hromkovic, J., Kneis, J., Kupke, J., Proietti, G., & Widmayer, P. (2007). On the Approximability of TSP on Local Modifications of Optimally Solved Instances. Algorithmic Operations Research, 2(2), 83. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/2803


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 U, let LM-U (local-modification-U) denote the same problem as U, but in LM-U, 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-U than for U. 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 β-triangle inequality (LM-Δβ-TSP) remains NP-hard for all β>½. However, for LM-Δ-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<β<3.34899, we achieve a better approximation ratio for LM-Δ-TSP than for Δβ-TSP. For ½≤β<1, we show how to obtain an approximation ratio arbitrarily close to 1, for sufficiently large input graphs.