概要とあらすじ
近似アルゴリズムについての本です．近似アルゴリズムに関しては，すでにWilliamson Shmoysによる教科書
があるのですが，本書はこのWilliamson Shmoysへの橋渡しをする本として書かれたそうです．
この本は大きく分けて３つの部分に分かれておりまして，１つめの部分では近似可能性クラスについての話が紹介されます．問題を，どのくらいの精度で近似できるかによって分類するという話です．P≠NPが証明できていない以上，分類は仮のものに過ぎないわけですが，多項式時間還元だけを考えているうちはNP完全問題同士は同じくらいの難しさであるように見えるので，NP完全問題の間にも難しさの違いがあるというのがわかるという点にあたりまえでない要素があります．
近似可能性クラスについて議論する際には「このクラスよりも難しい」という近似下界を証明するのが最も技術的に難しく興味深いところなのですが，本書ではそのあたりの進んだ話はWilliamson Shmoysなど他の書籍に譲り，概略のみ述べるにとどめたものが多いです．
2つめの部分では，線形計画問題の基礎と，その近似アルゴリズム設計・解析への応用が述べられています．線形計画問題は本当に重要なトピックで，近似アルゴリズムの設計に使えるのみならず，解析に使うこともできます．本書では，そうした線形計画問題の応用が述べられています．特に，線形計画問題とは一見関係のないアルゴリズムの解析で出てくるのがおもしろいですね．
3つめの部分は．確率的手法の紹介です．乱択ラウンディング技法が主として紹介されています．
総評
結論を先に言ってしまうと，あまり良い本だとは感じませんでした．
近似アルゴリズムの勉強をされたい方は，ちょっと高価ですけど素直にWilliamson Shmoysを読まれた方が良いと思います．
独自性がない
ただでさえ内容的にWilliamson Shmoysとの重複が多いのに，技術的に難しい結果の証明を省略して「詳しくはWilliamson Shmoysをみてね」で済ませている部分も多いので，この本を読む意義が感じられなくなっています．
Williamson Shmoysは確かに難度の高めな書籍なのですが，直観的なイメージの説明はむしろWilliamson Shomoysの方が多いくらいなので，あの本で挫折したひとがこの本で救われるとはちょっと思えません．唯一この本の方が充実しているのは計算の具体例くらいですが，だから何？という気がします．
演習問題がザツ
加えて，この本は演習問題にかなりの問題があります．読んでいていちばんイライラさせられたのがここです．演習問題の質が露骨に低いと，解こうというモチベーションが下がってきますね．
よく知られた定理をそのまま引用
よく知られた定理をそのまま引用し，「示せ」とだけ書いてある問題があります．演習問題のネタが思いつかなかったのだと思いますが，よく知られてる結果は読者としてはあんまり導きたくないので，派生形を考えさせるとか工夫をすべきだったと思います．
本文に解法への導線がない
いくらなんでも不親切すぎます．「本文を丁寧に読んで，本文で紹介された技法を少し変えて用いれば解けるように作ってあるだろう」と読者は想定しているんです．本文にないテクニックを用いる問題を出さないでください．ちょっと常識を疑うレベル．
おまけ：演習問題の解答
ついでなので，演習問題への略解を載せておきます．
１章の演習問題
1-7-1 完了時刻最小化スケジューリング問題
計算するだけなので省略．最適解の値も，処理時間の総和の平均に一致するためすぐにわかる．
1-7-2 巡回セールスマン問題
最適解が本当に最適であることを証明する必要がある．
$N_1$ の場合は，重み１の辺だけではHamilton閉路がないことを示せばよい．そのためには，どんなHamilton閉路も重み１の辺からなるグラフの内側と外側を行ったり来たりしないといけないが，そうすると必ず訪れることのできない頂点が出てしまうことを確認すればOK．
$N_2$ の場合は，重み１の辺だけを通るHamilton閉路がある．
1-7-3 点カバー問題
最小点カバーのサイズを決定しないといけない．
$N_1$ については，２と同様グラフを内側と外側に分けて考えれば $OPT = 6$ がいえる．
$N_2$ については，グラフを５つの同型なグラフが連結されたものと見なしてやれば $OPT = 12$ が証明できる．
1-7-4 点カバー問題に対する貪欲法
計算するだけなので省略．
1-7-5 最大有向無閉路部分グラフに対する２近似アルゴリズム
各頂点 $v \in V$ に対して番号を振り，$V = \{ 1, 2, \cdots , n \}$ とする．そうしておいて，各有向辺 $e \in E$ を，番号の大きい方から小さいほうへ向かっているのか，あるいはその逆なのかによって分割する．
そうして得られる分割を $E = E_1 \cup E_2$ とする．$E_1$ と $E_2$ のうち，サイズが大きい方を $A$ とする．$A$ は，番号が大きくなる辺または小さくなる辺しか含まないので，閉路をもたない．
このとき次が成り立つ：
したがって $A$ を返すアルゴリズムは近似比２を達成する．このアルゴリズムが多項式時間で停止することは明らかだろう．
1-7-6 最小極大マッチング問題に対する２近似アルゴリズム
極大マッチングをなんでもいいから求めて，それを返せばよい．
これが２近似であるのは，そもそもどんなマッチング $T$ と極大マッチング $S$ についても $|T| \leq 2 |S| $ だからである． （独立性システムにおいて最良選択貪欲法の近似率がランク商以上になることを使用してもよい．この問題は，辺重みが１でなくても近似率が２になる）
$S \cap T = \emptyset$ かどうかで場合分けをする．
まず $S \cap T = \emptyset$ のケース．$e \in T$ をとる．仮定より $e \not\in S$ である．$S$ は極大なので，$S + e$ はマッチングではない．したがって $S$ のある辺 $e'$ と $e$ は交わりを持っている．そのような $e'$ は一意とは限らないが，候補からひとつを選ぶことによって写像 $f : T \to S$ が定義できる．
$T$ はマッチングなので，各辺 $e \in S$ に対して $e$ における $f$ の逆像のサイズは高々２である． したがって \begin{align} |T | &= \sum_{e \in S} |f^{-1}(e)| \\ &\leq 2 |S| \end{align} がいえた．
次に $S \cap T \not= \emptyset$ のケース．$U = S \cap T$ とする．元のグラフ $G$ から $U$ に属する辺と，そこに繋がる辺をごっそり引き抜いたものを $G \setminus U$ と書くことにする．このグラフ $G' := G \setminus U$ において $S \setminus U$ は極大マッチングなので，上記の証明を再び適用することができて，$| T \setminus U | \leq 2 |S \setminus U|$ が言える．
したがって $|T| \leq 2|S| - |U| \leq 2|S|$ が成り立つ．これで示すべきことがいえた．
２章の演習問題
2-7-1 最小二分割問題
アルゴリズム2.1を走らせよと書いてあるが，$\varepsilon$ をどういう値にとれば良いのか指定がない．読者が任意に設定してよいということか．
最適解の値は302である．
2-7-2 最小ビンパッキング問題
最適解の値は９．
2-7-3 最小ビンパッキング問題
最適解の値は10.
３章の演習問題
3-7-1 ナップサック問題
最適解の値は4万0700．
3-7-2 ナップサック問題に対する貪欲アルゴリズムの近似保証
アルゴリズムは容量あたりの価値が最大になるように品物を選んでいるため，$X^ g$ について次が成り立つ．
$Y_j := \{ 1,2 , \cdots , j\} \cap Y$ とする．$j$ についての帰納法で示せる．
次も $X^ g$ についての性質である．近似比はいくらでも悪くなり得るが，絶対誤差は価値の最大値で抑えられる．
最適解を $\mathcal{O}$ とし，$\mathcal{O} \not= X^ g$ であるものとする．$\mathcal{O}$ は最適解なので，$\mathcal{O} \subset X ^g$ はありえない．したがって最適解から外されている品物 $j \in \mathcal{O} \setminus X ^g$ が存在する．
$X ^g$ の極大性により，$a(X ^g ) + a_j > b \geq a(\mathcal{O})$ である．ゆえに $a( \mathcal{O} - j ) < a(X ^ g) $ である．そこで補題により $c( \mathcal{O} - j ) \leq c(X ^ g) $ であることがわかる． 以上の議論により $$ OPT - c(X^ g) \leq c_{\mathrm{max}} $$ が成り立つことがわかる．
ここまでくれば結論は自明である．定義から $c(X ^a ) \geq c_{\mathrm{max}}$ なので，
$OPT \leq c(X^ g) + c_{\mathrm{max}} \leq 2 c(X^ a)$ が成り立つ．
3-7-3 定理3.3の証明補完
最大化と最小化を変えるだけなので省略．
3-7-4 完了時刻最小化問題は強NP困難
3-partition からの帰着により示せる．しかし本文中で3-partitionには触れられていないため，この問題は出題ミスである．
４章の演習問題
4-5-1 最小支配集合問題の近似可能性クラス
難しくない．後回し．
５章の演習問題
5-6-1 双対の双対は主問題
難しくない．また，よく見かける問題でもある．よって省略．
5-6-2 LP標準形への帰着
難しくない．後回し．
5-6-3 Königの定理
組合せ的な証明がある．アルゴリズムデザイン などを参照すればよい．
線形計画問題の強双対定理を利用して証明することもできるが，そのためには２部グラフの接続行列が完全ユニモジュラ行列であることを利用しなければならない．*1本文中ではその話は説明していないので，これは出題ミスである．
６章の演習問題
6-9-1 確定的ラウンディングアルゴリズムのタイトな例
台集合 $X$ と集合族 $S_{di}$ $(0 \leq d \leq f-1, 1 \leq i \leq 2^ d)$ を次のように定める．
そうしておいて集合 $S _ {di}$ の重み $w _ {di}$ を $w _ {di} = 1/2^ d$ で定義する．このように定義したインスタンスがタイトな例となる．
6-9-2 確定的ラウンディングアルゴリズムの変形
相補性原理から従う．
6-9-3 集合カバー問題のLPの整数性ギャップが最大包含回数と一致するタイトな例
台集合 $X$ を整数の部分集合ではなく，部分集合の族として次のように定義する．
$X$ の部分集合族 $\mathcal{C}$ は，各点 $v \in V$ に対する $S _ v \subseteq X$ からなる．$S _ v$ とは $v$ を含む $X$ の元全体として定義される．つまり
であるものとする．重みはすべて１とすればよい．このように定めたインスタンスがタイトな例となる．
6-9-4 主双対法のタイトな例
台集合 $X$ を $f+1$ 個の点の集合として次のように定める．
$X$ の部分集合の族 $S_j$ は以下のようにする．
重みは $w_i = 1 $ $(1 \leq i \leq f-1)$, $w_0 = 1 + \varepsilon$ で定める．$\varepsilon$ を０に近づけていくと，近似比が $f$ に漸近する．
6-9-5 集合カバー問題のLPの整数性ギャップが最大集合サイズの対数に一致するタイトな例
わからん
6-9-6 カバー最大化問題
近似アルゴリズムデザインの演習問題2.11 を参照のこと．劣モジュラ関数の性質を使えば証明できる．浅野「近似アルゴリズム」では劣モジュラ関数の話をしていないので，誘導が不親切であると思われる．
*1:完全ユニモジュラ行列とその線形計画問題との関連については，岡本吉央先生の2014年度の離散最適化基礎論の講義スライドを参照のこと
