M. Bellare:
Proof Checking and Approximation: Towards Tight Results, 1996.
Slightly expanded version of a survey that appears in the Complexity Theory Column of
Sigact News, Vol. 27, No. 1, March 1996. It describes recent developments, stating the best known non-approximability results and explaining how they are being derived.
P. Crescenzi and V. Kann:
"A list of NP-complete optimization problems"
This is a compendium of NP optimization problems and their approximation complexity, containing about 150 problems. In HTML format. The file is also available in
DVI format
Other Links
- PCP and Approximation
Pointers to survey articles on probabilistically checkable proofs and their application to approximation (about 10 different surveys), maintained by Mihir Bellare.
