PERFORMANCE GUARANTEES FOR APPROXIMATION ALGORITHMS DEPENDING ON PARAMETRIZED TRIANGLE INEQUALITIES

The worst-case analyses of heuristics in combinatorial optimization ar e often far too pessimistic when confronted with performance on real-w orld problems. One approach to partially overcome this discrepancy is to resort to average-case analyses by stipulating realistic distributi ons 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 f or establishing approximation algorithms with fixed performance guaran tee. Now, a parametrized form of the triangle inequality has a conside rably larger range of applicability and allows the prediction of the h euristics performance, where otherwise no bound could be provided. For example, it is interesting to observe that two well-known approximati on algorithms for the Traveling Salesman Problem (TSP), assuming the t riangle inequality, behave differently when one relaxes the imposed tr iangle inequality. The double-spanning-tree heuristic can be adjusted (by suitably extracting a Hamilton circuit from a Eulerian walk) to yi eld an approximation algorithm with performance guarantee increasing q uadratically with the parameter governing the relaxed triangle inequal ity. The Christofides algorithm cannot be modified in this way and hen ce does not tolerate a relaxation of the standard triangle inequality without loosing the bound ori its relative performance.