Numerous practical problems are integer optimization problems that are intractable. Such problems are commonly addressed with heuristics that provide a solution, but not information on the solution's quality. The approximation algorithms' framework provides a guarantee on the quality of the solution obtained. This framework has been used as a guide to developing algorithms in specific problem areas with increasingly improved performance. The book describes the state-of-the-art algorithms in each specialized area and reviews the most effective technical tools used. The thirteen chapters of the book are written by leading researchers that have contributed to the state of the art of approximation algorithms.
Back to Hochbaum main page