[筆記] Design and Analysis of Approximation Algorithms - Introduction

標題其實是這本書：Design and Analysis of Approximation Algorithms，這本書簡單來說是在介紹 approximation algorithm (中文好像會翻成逼近演算法、近似演算法)。這類演算法著重的地方是那些現在沒有 "有效率" (也就是 polynomial time 的方法) 的方法解決的最佳化問題 (optimization problem，換言之答案是要找出極值，不論是最大值或最小值)，這類問題只要去找 NP-Complete、NP-hard 就有一大堆了。

當然學術上的方法是一回事，現實中當你遇到這類問題又一定要有一個解的時候，真正的問題就會變成你怎麼知道你找出來的解距離最佳解有多遠? 所以這本書的目的就是統整併分析目前有哪些方法可以有效率的解決找出一個近似解、同時告訴你這些近似解在理論上距離最佳解有多遠?

第一章起手式是用常見的背包問題 (knapsack problem)：

給你 $n$ 個物品 ($I_1, I_2, ...I_n$) 和一個容量上限 $S$ 的背包，已知每個物品的大小及價值分別是 $s_i$ 及 $c_i$，問你這個背包能裝的物品總價值最高是多少? 而條件限制是物品無法被分割。

整個章節其實就是圍繞著這個背包問題在探討何謂 approximation algorithm

首先假設我們忽略背包問題中的限制：物品不能分割，那這問題就變得很簡單

1. 先算出每個物品 $I_i$ 每單位大小 (我們就先別管是體積還是面積還有疊起來有空隙這回事) 的價值 (為了方便稱呼，就叫他密度好了) $d_i = c_i / s_i$
2. 根據 $d_i$ 從大到小排序，從密度最大的開始依序往下放進背包，直到背包放滿。如果放到第 $k$ 個物品時發現沒辦法完整的放進去，那就分割這個物品讓它恰好可以裝滿這個背包
   

這個方式是常見的 greedy algorithm，在忽略條件限制下我們可以證明這個方法拿到的總價值一定最高，而且速度很快。但是如果把條件放進來考慮呢? 最常見的作法是 dynamic programming (DP)，概念可以參考演算法筆記裡面有完整的流程說明。

雖然 DP 的方法可以找到最佳解，但是隨著物品數量及其總重量 (特別是重量這點) 會讓所需時間大幅上升，在城市時間是個重大考量的前提下通常不太可能真的讓你用 DP 找最佳解，用上面提到的 greedy algorithm 還比較可行。

然而，前述的 greedy algorithm 因為是忽略物品不可分割這個限制的，因此在這裡的背包問題物品是不能分割的情況下，這方法就被調整成如果放到第 $k$ 個物品時發現不能完整放入，那就不放並結束 (所以背包內有依據 $d_i$ 從大到小排序過後的前 $k-1$ 個物品)。而原本的 greedy algorithm 就變成了 greedy strategy (兩者差在能不能保證找到最佳解)

這本書的第一個要介紹的重點就是上面的 greedy strategy：他們有證明這方法找出來的解 (假設是 $C_G$)，跟最佳解 (假設是 $C_{opt}$) 滿足 $C_{opt} \leq 2 C_G$。證明就請自己看書或是上網找找有沒有好心人士寫囉，不過基本概念是 $C_G \leq C_{opt} < C_G + c_k / s_k$ (假設如上面說的，用 greedy strategy 背包內最多能放密度最大的前 $k-1$ 個物品)

在這邊他們提出了一個概念：performance ratio，白話一點就是近似解最差會是最佳解的幾倍，以上面的例子來說，greedy strategy 在這裡的背包問題的 performance ratio 是 2

當然，既然可以證明出 performance ratio，接下來的挑戰就是有沒有辦法把這個值縮小? 其中一種方式是想一套新的方法或是改良既有方法，證明新方法的 performance 比較小；另一種方法是先訂定一個容許的誤差值 (假設是 $a$)，讓 performance ratio 及 runtime 都跟這個 $a$ 掛勾 (當然，$a$ 是一個定值)，如果 $a$ 越小、performance ratio 就越小、runtime 就越久 (但，還是 polynomial time)，反之亦然。

以上面的例子來說，我們定好 $a (0 < a \leq 1)$ 後，先利用一次 greedy strategy 找出 $C_G$，然後把物品分成兩堆：$c_i \leq a C_G$ 的一堆 (假設是 $I_X$，剩下的另外一堆 (假設是 $I_Y$)。而我們把前面 greedy strategy 套用在 $I_X$ 這堆、DP 套用在剩下的 $I_Y$ 這堆。

這個方法的 performance ratio 就變成 $1+a$，時間複雜度則是 $O(n^{1+2/a}log(nMS))$，其中 $M = max\{c_k | 1 \leq k \leq n\}$，這邊因為 $a, M, S$ 都是常數，所以實際上依然是 polynomial time，但是隨著 a 越來越小，時間複雜度會隨之上升，當然找到的解就會越趨近最佳解。

最後，我們可以注意的是像這邊利用 greedy strategy 的方式是把條件放鬆，雖然 solution space 因此而加大，但這反而讓這個問題簡化得以用有效率的方式找到一組解，這種作法被叫做 relaxation。其他的範例就像是 integer linear programming (ILP) 用 linear programming (LP) 去找近似解，也是類似的概念。只是 relaxation 的一個重點在於因為找近似解時放鬆了條件限制，所以我們必須把這組近似解調整到滿足條件限制，以上面背包問題的 greedy strategy 就是放棄無法完整放入的物品；而用 LP 找出來的近似解則是必須把浮點數的解轉成整數來滿足 ILP 的條件。當然這個轉換過程的時間複雜度也必須要是 polynomial time 才行。

相對於 relaxation，另一種作法則是 restriction，也就是縮小 solution space 的概念，比方說把整個問題利用 partition 分割成數個小問題來各自求解，最後再統整起來。要舉例的話，我覺得 FLUTE 就挺有這種精神的。(當然，FLUTE 這篇論文裡面是沒有證明 performance ratio 這種東西的)。這邊特別值得注意的是通常 restriction 不需要額外的操作，因為是直接把條件變得更嚴格，所以找出來的解必定符合原先相對寬鬆的條件，是以跟 relaxation 的作法相比，他少了轉換近似解到符合原先條件的這個過程。

以上，是這本書的簡介，接下來會不會有每個章節的簡介就...看我能不能提起勁來寫 XD