Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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.

ISSN 1433-8092 | Imprint