Survey on Hardness of Approximation

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.

About these ads

13 thoughts on “Survey on Hardness of Approximation

  1. You misspelled “Krauthgamer” in the Acknowledgements. Miklos has an accent in [AD97] but not in [AKS01].

  2. page 28, “Feige consider the 3SAT problem” should be “Feige considers the 3SAT problem”

  3. 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.

  4. 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.

  5. 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.

  6. 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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s