|
Abstract : |
This chapter is a self-contained survey of recent results about the hardness of approximating NP-hard optimization problems. 1 This chapter surveys recent results on the hardness of approximating NP-hard optimization problems. According to these results, computing good approximate solutions to many problems is NP-hard--- and hence no easier than computing exact solutions. In general, proving the NP-hardness of an optimization problem involves a reduction from SAT (or any other NP-complete problem) to the problem. To prove the hardness of approximation, this reduction must produce a gap in the value of the optimum. For instance, proving the NP-hardness of approximating the maximum clique problem within a factor g requires coming up with a reduction from SAT to CLIQUE that maps satisfiable formulae to graphs with clique number at least K (for some K), and unsatisfiable formulae to graphs with clique number at most K=g. For a long time it was unclear how to construct such gap producing reductions for Clique and many other important optimization problems. The Cook-KarpLevin [Coo71, Kar72, Lev73] techniques for doing reductions seemed more suited, |
