本書は,近似アルゴリズムデザインの技法とアイデアを系統的かつ明快に解説している。 第1部では,単純な問題を例にとり,これらの技法とアイデアを具体的にわかりやすく解説している。第2部では,これらの技法とアイデアを実際のケースで生じるより高度な問題に適用する際の工夫を具体的に解説している。
本書において系統的な解説を可能にしているのが,線形計画法と整数計画法である。欧米の大学では,本当に実用的なアルゴリズムの研究開発には,これらの分野が極めて重要であることが認識されてきている。したがって,情報科学系でもこれらを講義で取り上げる大学が増加してきていて,本書もそれに後押しされて,その重要性を増してきている。すなわち,これからのアルゴリズム教育には,線形計画法と整数計画法の概念の理解とそれを応用する能力の育成が必要不可欠となると思われるが,本書はそれらも自然に身につくように記述されている。
(David P. Williamson, David B. Shmoys:The Design of Approximation Algorithms, Cambridge University Press, 2011)