Andreae, Thomas; Bandelt, Hans-Jürgen Performance guarantees for approximation algorithms depending on parametrized triangle inequalities. (English) Zbl 0832.90089 SIAM J. Discrete Math. 8, No. 1, 1-16 (1995). Summary: The worst-case analyses of heuristics is combinatorial optimization are often far too pessimistic when confronted with performance on real-world problems. One approach to partially overcome this discrepancy is to resort to average-case analyses by stipulating realistic distributions of input data. Another way is to incorporate a priori information on the potential domain of the input data, for instance, assuming the triangle inequality for input matrices is in some cases instrumental for establishing approximation algorithms with fixed performance guarantee. Now, a parametrized form of the triangle inequality has a considerably larger range of applicability and allows the prediction of the heuristics performance, where otherwise no bound could be provided. For example, it is interesting to observe that two well-known approximation algorithms for the Traveling Salesman Problem (TSP), assuming the triangle inequality, behave differently when one relaxes the imposed triangle inequality. The double-spanning-tree heuristic can be adjusted (by suitably extracting a Hamilton circuit from a Eulerian walk) to yield an approximation algorithm with performance guarantee increasing quadratically with the parameter governing the relaxed triangle inequality. The Christofides algorithm cannot be modified in this way and hence does not tolerate a relaxation of the standard triangle inequality without loosing the bound on its relative performance. Cited in 3 ReviewsCited in 28 Documents MSC: 90C27 Combinatorial optimization 90C35 Programming involving graphs or networks 68R99 Discrete mathematics in relation to computer science Keywords:performance guarantee; parametrized triangle inequality; minimum Steiner tree; anticlustering; traveling salesman; worst-case analyses of heuristics; approximation algorithms PDFBibTeX XMLCite \textit{T. Andreae} and \textit{H.-J. Bandelt}, SIAM J. Discrete Math. 8, No. 1, 1--16 (1995; Zbl 0832.90089) Full Text: DOI