Computing near-optimal solutions to combinatorial optimization problems

In the past few years, there has been signiicant progress in our understanding of the extent to which near-optimal solutions can be ee-ciently computed for NP-hard combinatorial optimization problems. This paper surveys these recent developments, while concentrating on the advances made in the design and analysis of approximation algorithms, and in particular, on those results that rely on linear programming and its generalizations. In the past few years, there have been major advances in our understanding of performance guarantees for approximation algorithms for NP-hard combina-torial optimization problems. Most notably, after twenty-ve years of essentially no progress, a new technique has been developed for proving that certain approximation algorithms are unlikely to exist. Partially in response to this development , there have also been signiicant recent advances in the design and analysis of approximation algorithms. In this survey, we will outline a few of the areas in which progress has been made, and suggest directions in which there is still interesting work to be done. The central deenition of this survey is that of a-approximation algorithm for an optimization problem: a polynomial-time algorithm that delivers a feasible solution of objective function value within a factor of of optimal. The study of approximation algorithms predates the theory of NP-completeness. Some early results, such as the proof due to Vizing (1964) that a graph always has