ABSTRACT
The design of approximation algorithms has evolved as one of the most successful approaches for dealing with hard optimization problems. Already a short time after introducing NP-hardness (and completeness) as a concept for proving the intractability of computational problems [1, 2], the first successful approximation algorithms were proposed [3, 4, 5, 6]. Since then, a wealth of approximation algorithms for very many practically relevant problems have been developed, as large parts of this handbook stand witness to. Overviews on approximation algorithms can be found, for example in References 7, 8, 9, 10, 11, 12.
