Computing Near-Optimal Solutions to Combinatorial Optimization Problems

. In the past few years, there has been significant progress in our understanding of the extent to which near-optimal solutions can be efficiently 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 combinatorial optimization problems. Most notably, after twenty-five 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 significant recent advances in the design and analysis of approximation algorithms. In this survey, we will outline a few of the areas in whi..