Probabilistically Checkable Proofs and Approximation

Background The NP-completeness of important optimization problems focused research effort on the design of approximation algorithms. Some problems succumbed to approximation. Others, however defied all efforts to either find good approximation algorithms or to show such algorithms don't exist. A breakthrough came in a 1991 paper by Feige, Goldwasser, Lovasz, Safra, and Szegedy. They used results on probabilistically checkable proofs (PCPs) to show that Max Clique is hard to approximate. Research has since then expanded to apply their approach to other problems, and to improve the results. Today, the known results are quite amazingly broad and strong, and research is still advancing rapidly.

Pointers Over the past few years, much has been written on this subject. Below are pointers to some relevant survey articles and their authors. Clicking on the article name typically brings up a postscript file, or, if one is not available, information on the best source I know to get the article. Comments and pointers to additional sources appreciated.