Q: When is the book going to be published?
A: The book is now available for order.
Q: What makes this book different from other previous books on approximation algorithms?
A:

One of the main differences is that the book is organized around algorithmic technique. We try to show that when designing an approximation algorithm for a new discrete optimization problem, there are a standard set of techniques that one can bring to bear.

While there is some amount of overlap in results presented in other books (reflecting consensus in what the field views as the important results and techniques), because of our interests in the field there is more coverage of scheduling problems (especially single machine scheduling) and semidefinite programming.

Simply because the book is more recent, it has some coverage of the unique games problem and the unique games conjecture. The book also covers recent results on uniform sparsest cut (the Arora-Rao-Vazirani result), minimum bisection (due to Racke), and some of the recent work on the minimum Steiner tree problem. The book covers the probabilistic embedding of metrics into tree metrics result of Fakcharoenphol-Rao-Talwar that is now a standard technique in the field. It also covers recent work on minimum-cost bounded-degree spanning trees, and the local search algorithms for facility location and k-median problems.

Also because the book is more recent, it can give simplified proofs that didn't appear in the original papers. For instance, the proof for the survivable network design algorithm of Jain has a simplified proof that was devised just a few years ago.

A final difference is that the book's organization shows how different techniques can lead to improved results. The book returns several times to the facility location problem, prize-collecting Steiner tree problem, bin-packing problem, among others, showing how a new technique gives an improvement over previous results.

Q: What is the image on the book cover and the webpage supposed to represent?
A: It's a graphic representation of the tree metric algorithm of Fakcharoenphol, Rao, and Talwar. The graphic was generated by some code of Frans Schalekamp.