Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. (English) Zbl 0961.68058

Bongiovanni, Giancarlo (ed.) et al., Algorithms and complexity. 4th Italian conference, CIAC 2000, Rome, Italy, March 1-3, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1767, 72-86 (2000).
Summary: The investigation of the possibility to efficiently compute approximations of hard optimization problems is one of the central and most fruitful areas of current algorithm and complexity theory. The aim of this paper is twofold. First, we introduce the notion of stability of approximation algorithms. This notion is shown to be of practical as well as of theoretical importance, especially for the real understanding of the applicability of approximation algorithms and for the determination of the border between easy instances and hard instances of optimization problems that do not admit any polynomial-time approximation.
Secondly, we apply our concept to the study of the traveling salesman problem. We show how to modify the Christofides algorithm for \(\Delta\)-TSP to obtain efficient approximation algorithms with constant approximation ratio for every instance of TSP that violates the triangle inequality by a multiplicative constant factor. This improves the result of T. Andreae and H.-J. Bandelt [SIAM J. Discrete Math. 8, No. 1, 1-16 (1995; Zbl 0832.90089)].
For the entire collection see [Zbl 0933.00042].


68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C35 Programming involving graphs or networks


Zbl 0832.90089