Error-Analysis of Heuristic Algorithms by Simulation

Approximation-algorithms (heuristics) are important in time-critical ap- plications. The selection of a suitable heuristic depends on the expected error. Theoretical results for approximation-algorithms mainly deal with worst-case-estimations of the error. By simulation of the application-environment information about the error-behaviour of the application data can be obtained. The influence of parameters on the error-behaviour of different heuristics for the Travel ling-Salesman-problem have been analysed by this method.