Combinatiorial Approximation Algorithms

START project Y 43 Combinationrial Approximation Algorithms Gerhard WÖGINGER 28.06.1996 In principle it is possible to solve *every* algorithmic problem and *every* optimization problem in the "real" world by an appropriate computer program, as long as we have (a) a sufficient amount of computation time and a sufficient storage capacity available, and as long as we know (b) the complete problem data. However, in practise these two conditions are usually not fulfilled: Nobody is willing to wait 200 years for the result of a computer program, and nobody knows today what data tommorrow will bring. In these cases, one is usually satisfied with an approximate solution, i.e., with a solution that comes "reasonably close" to the optimal solution and that is easy to compute. The research project investigates how to approach the global optimum under incomplete information and under severe restrictions on the running time. Time complexity and quality of solution algorithms are measured with the tools of theoretical computer science.

During this project, we have analyzed the approximability behavior of a huge number of combinatorial optimization problems. Most of these optimization problems come from the area of scheduling, the area of graphs and networks, and the area of facility location. We have derived positive and negative results: The positive results are approximation algorithms and approximation schemes that find within a reasonable amount of computing time a solution that is reasonably close to the optimal solution. The negative results provide the non-existence of fast approximation algorithms for certain optimization problems subject to certain hypotheses from computational complexity theory. All our results are of theoretical nature and concern the fundamentals of computation. Hence, they do not have any direct applications to economics, society, or culture. In most of our results, we investigate isolated problems, and derive highly specialized results that are based on their specific properties. As one of our most general main results, we have characterized the situations where a certain data rounding method yields approximation algorithms of arbitrarily good quality (a so-called FPTAS). This provides a unified theory of dynamic programming approaches that can be translated into FPTASs. Moreover, we have performed a structural analysis of the existing approaches to approximation schemes in the literature. We have classified them into three basic techniques: The technique of rounding the input data, the technique of structuring the output space, and the technique of simplifying the data stored during the execution of an exact algorithm.