Hardness of approximation

MAX-SNP problems: with constant approximation but no PTAS.

Examples: MAX-3SAT, Metric TSP, Max Clique on bounded degree graphs.

PCP theorem basically proves that MAX-3SAT, thus all MAX-SNP-complete problems, has no PTAS unless P=NP.

A good course webpage:

http://www.cc.gatech.edu/~khot/pcp-course.html