Hardness of Approximation
Teofilo F. Gonzalez · 2007
This chapter is devoted to the core theory of inapproximability. Undoubtedly, the most fundamental part of the theory, with its numerous consequences, is the probabilistically checkable proofs (PCPs) theorem, which asserts that MAX-3SAT is NP-hard to approximate within a factor of 1 + (for some > 0). In Section 17.9 we sketch a recently obtained short proof to it [1].