書評

2002年 02月 01日 書評 増山 繁 Shigeru Masuyama （豊橋技術科学大学知識情報工学系） 著者 : Vijay V. Vazirani 書名 : Approximation Algorithms 出版 : Springer 2001/ISBN 3-540-65367-8 スケジューリングを始め，産業界等で解くことが要請される問題の多くがNP困難，すなわち，厳密解を求める効率の良いアルゴリズムが存在しそうにないと信じられている問題である．しかしながら，現実には，最適解が求まらないからといって手をこまねいている訳にはいかない．実際，最適解でなくてもそこそこ良い解で使えるものが欲しいことがよくある．そのような解を多項式時間で求めるアルゴリズムを近似アルゴリズムという．現在の厳しい経済情勢の下，大幅のコスト削減を迫られている現場では，最適解との誤差が見積もれればもっとありがたい．そのような精度保証のある効率の良い近似アルゴリズムを求める研究は，最近活発に研究されてきている．本書は，それを体系的に学ぶことができるように書かれた本格的な入門書で，出版が待ち望まれていた待望の書である．素材の選択と配列，説明に工夫が施されており，本書を学ぶことで現実に遭遇する問題に対して，適切な精度保証つき近似アルゴリズムを設計するための基礎知識を身につけることができる．各章が10ページ程度と短いので，講義や研究室のセミナーのテキストとして好適で，特に，日常業務に追われてまとまった時間がとれない方も，少しずつ時間を見つけて勉強できるのは嬉しい．文献リストも充実していて，より進んだ勉強をするのにも便利である．特に，Notesにおいて，歴史的話題を紹介しており，大変興味深い．現場で問題解決に迫られている技術者，近似アルゴリズムについて基礎から体系的に学ぼうとする学生，研究者に是非一読をお勧めしたい． 計算困難問題に挑戦する手法として，近似アルゴリズムの他に，メタヒューリスティックスもあるが，それと比較した時の近似アルゴリズムの特徴は以下の通りである． メタヒューリスティックスでは，計算時間の保証がされていないものが多いのに対し，近似アルゴリズムでは，多項式時間で解が求まることが保証されている． 解の精度が保証されている場合が多い． メタヒューリスティックスでは，良い解を得ようとすると，実装の際，経験と勘に基づいたチューニングを要する場合が多いが，近似アルゴリズムは比較的容易に実装できるものが多い． 本書の目次を本稿の最後に掲げる．Part I. Combinatorial Algorithmsでは，対象とする問題固有の構造的特徴を活用した多様な組合せ的近似アルゴリズムが紹介されている．Part II. LP-Based Algorithmsでは，最も基本的な近似アルゴリズム設計法の一つであるLP (Linear Programming) 緩和に基づいた手法が説明されている．具体的には，緩和問題である線形計画問題の解の整数値への丸め，及び，主双対算法に基づく方法が紹介されている．最後に，それを用いることでいくつかの問題に対して非常に精度の良い近似アルゴリズムを得ることに成功したことから最近注目を集めている半正定値計画法(Positive Semidefinite Programming) による緩和であるSDP緩和が紹介されている．Part III. Other Topicsでは，格子点上での最短ベクトルの近似，数え挙げの近似が紹介され，更に，PCP (Probabi- listically Checkable Proof Systems) 定理等の近似可能性の理論が説明され，P=NPでないとの仮定の下でのSet Cover問題の近似困難性が説明されている．最後にいくつかの未解決問題が紹介されている． なお，入門書である本書を読了し更に進んで勉強されたい方には，専門書としてD. S. Hochbaum, eds., Approximation Algorithms for NP Hard Problems, PWS Publishing Company, 1997をお勧めしたい．これは，Chapter 1がApproximation Algorithms for Schedulingとなっているのも嬉しい． 1 Introduction Part I. Combinatorial Algorithms 2 Set Cover 3 Steiner Tree and TSP 4 Multiway Cut and k-Cut 5 k-Center 6 Feedback Vertex Set 7 Shortest Superstring 8 Knapsack 9 Bin Packing 10 Minimum Makespan Scheduling 11 Euclidiean TSP Part II. LP-Based Algorithms 12 Introduction to LP-Duality 13 Set Cover via Dual Fitting 14 Rounding Applied to Set Cover 15 Set Cover via the Primal-Dual Schema 16 Maximum Satisfiability 17 Scheduling on Unrelated Parallel Machines 18 Multicut and Interger Multicommodity Flow in Trees 19 Multiway Cut 20 Multicut in General Graphs 21 Sparsest Cut 22 Steiner Forest 23 Steiner Network 24 Facility Location 25 k-Median 26 Semidefinite Programming Part III. Other Topics 27 Shortest Vector 28 Counting Problems 29 Hardness of Approximation 30 Open Problems Appendix A An Overview of Complexity Theory for the Algorithm Designer B Basic Facts from Probability Theory