Approximate book
There's a new book out by Williamson and Shmoys on approximation algorithms, The Design of Approximation Algorithms, available electronically for free as a pdf download.
For a book that claims to be a comprehensive reference on approximation algorithms, suitable for a general-purpose graduate course on the subject, it seems to me to have some strange lacunae. It has nothing about core-sets, for instance, and more generally very very little about approximation in geometric algorithms: the only such problem appearing in the table of contents is the Euclidean TSP. It also has similarly scanty coverage of competitive analysis of online algorithms, and absolutely nothing on streaming algorithms.
But if you want a book more specifically about how to bound the approximation ratio of linear and semidefinite programming relaxations to integer programming problems, this may be a worthwhile one to consider, despite the misleadingly general title. And the price is definitely right.
Comments:
2010-11-07T19:19:04Z
This criticism seems for the most part unreasonable. No book can cover approximation algorithms in every branch of TCS. If you include online algorithms and streaming algorithms, next you have to include approximation algorithms in algorithmic game theory, then online learning, then differential privacy, and so on. Where does it end? I think this book is about the "core" concepts that everyone from all these fields should know, and the authors made reasonable, yet obviously debatable, choices. I know everybody would like to think that their area is more "core" than all the others, but we could have that argument all day.
2010-11-07T19:22:16Z
I don't have any problem with the scope of the book being what it is. As you say, a book that covered all of approximation algorithms would have to be much bigger, and likely more unwieldy to use as a text. It's the title and the introduction that describe it as covering "approximation algorithms" without qualification that I see as more problematic.
2010-11-07T19:19:39Z
I am curious whether you think Williamson and Shmoy's selection of material is better than that of Vazirani: http://www.amazon.com/Approximation-Algorithms-Vijay-V-Vazirani/dp/3540653678/. It has ~115 fewer pages, but 13 more chapters. Of course, the quality of one's "selection of material" can differ greatly from the quality of its coverage. Being a subject that most any Computer Scientist should know, there seems to be a relative dearth of textbooks that cover this field adequately. There's also the Handbook of Approximation Algorithms and Metaheuristics that appears to be somewhat comprehensive: http://www.amazon.com/Handbook-Approximation-Algorithms-Metaheuristics-Information/dp/1584885505/. (By their nature, Handbooks tend to suffer from sufficient "quantity of coverage" but insufficient "quality of coverage".)
2010-11-07T19:24:20Z
I'm not actually very familiar with the Vazirani book. I thought Hochbaum's Approximation Algorithms for NP-hard Problems (really a collection of surveys rather than texts) had pretty good coverage, but it's very badly out of date by now.
2010-11-08T03:16:47Z
They come from a parallel universe that is more operation research oriented and exists for much longer (and is "deeper") than the newer topics you mentioned. We all live in a yellow submarine, etc... Probably a book trying to make a decent effort to cover all reasonable topics on approximation will be as large as the three volume book Combinatorial Optimization by A. Schrijver. Good luck writing such a book... ;) --Sariel
2010-11-11T19:25:03Z
DE - Thanks for the comments. Your certainly right that we don't say much about geometric algorithms; it was just too far from our expertise, and as Sariel points out above, we didn't try to attain Schrijver-like comprehensiveness (it took long enough to write as it was). I guess I view "online" and "streaming" algorithms as distinct fields of algorithmic research, though of course they also involve approximate computation; no intent to mislead there (neither Vazirani nor Hochbaum cover online or streaming algorithms either). -- David Williamson
2010-11-12T07:34:43Z
Thanks for the response. As for online and streaming algorithms: all online algorithms and a large proportion of streaming algorithms involve finding non-optimal solutions to optimization problems, with the quality of the solution measured by the ratio of its value to the optimal, so if that's not a form of approximation algorithm then I don't know what is.