In 2004 I wrote a survey on hardness of approximation as a book chapter for a book on approximation algorithm. I have just prepared a revised version for a new edition of the book.
While it would have been preferable to rethink the organization and start from scratch, because of time constraints I was only able to add sections on integrality gaps and on unique games, and to add references to more recent work (e.g. the combinatorial proof of the PCP theorem, the new 2-query PCPs, the tight results on minimizing congestion in directed networks, and so on).
If your (or your friend’s) important results are not cited, do let me know. The deadline to submit the chapter has long passed, but the threats from the editor haven’t yet escalated to the point where I feel that I have to submit it or else.
in theory 
on page 20, you mention
Dumer, Micciancio and Sudan
Who is Dumer? 🙂
You misspelled “Krauthgamer” in the Acknowledgements. Miklos has an accent in [AD97] but not in [AKS01].
“mistake”: Ilya Dumer is apparently a professor at UC Riverside.
Love the auto-link to other “hardness” related posts… 😉
oh God 😦
page 28, “Feige consider the 3SAT problem” should be “Feige considers the 3SAT problem”
Chyzhoy and Khanna’s hardness results for directed multicut and directed sparsest cut are good to mention, especially since the undirected versions are so well studied and important. When mentioning Set Cover hardness, it may be worth mentioning the 1-1/e-\eps hardness for the max coverage problem from Feige’s paper under the assumption that P\neq NP.
The work of Ben-Sasson and Sudan is missing in the references for nearly linear PCPs (on page 29). In fact, the nearly linear-sized PCP of Dinur (which is the best as of now) builds on the construction of Ben-Sasson and Sudan.
The hyperlinks in the PDF files don’t work!
Chuzhoy and Khanna’s hardness result on directed multicut and directed sparsest cut are worth including. Also, when discussing hardness of set cover, useful to mention the 1-1/e -\eps hardness for max-coverage under P\neq NP that is also in the Feige paper. It is especially interesting given the 1-1/e approximation that is now available for maximizing any given monotone submodular set function subject to any given matroid constraint, a far reaching generalization of the max-coverage problem.
Sam: the hyperlink problem seems due to some conversion done by the ECCC server; the links worked in the version I uploaded.
You can download a version with working links here:
Click to access inapprox2010.pdf
On page 27, “Schnither” should be “Schnitger”.
On page 29,
“Conversely, a (1+o(1))-approximate algorithm for Max 3SAT running in 2o(n) time would provide some evidence that the proof length in the PCP Theorem cannot be linear.”
should be
“Conversely, a (1+o(1))-approximate algorithm for Max 3SAT running in 2o(n) time would provide some evidence that the proof length in the PCP Theorem can be linear.”
Am I right?