The objective of this course is to learn about computational
complexity, not to just learn the contents of one book. Use the library.
Use the web. Do whatever works to learn. Just remember the one
rule: if you use other sources to complete an exercise, always cite the
sources and discuss how the sources contributed to your solution.
Copying a solution and presenting it as your own is plagiarism and, of course,
is simply not tolerated.
The following references come with thanks to Ming
I know of three books on approximation algorithms:
1. Approximation Algorithms for NP-Hard Problems by Dorit Hochbaum (Ed)
2. Approximation Algorithms by Vijay V. Vazirani
3. Complexity and Approximation - Combinatorial optimization problems and
their approximability properties by G. Ausiello, P. Crescenzi, G. Gambosi,
V. Kann, A. Marchetti-Spaccamela, M. Protasi
The first one is a collection of survey papers written by experts on
their respective fields; the second one is written by one person so it has a
more unified feel.
The third one is intended as an updated Garey and Johnson; it is both a
tutorial and a list of NP-hard problems. The problem list has a web page at
http://www.nada.kth.se/~viggo/approxbook/, which I often use as a reference.
The tutorial part is not that great: I learned about the PCP theorem from
this book and it took me a whole week to understand the thing; I then read
Arora's thesis and found that a good story had been spoiled by these lousy
story-tellers.
All three books are available in MSU library.