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
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 Andreae and Bandelt.