近似演算法設計

引用

Williamson, D. P., & Shmoys, D. B. (2011). The Design of Approximation Algorithms. Cambridge University Press. 作者提供的免費電子版：https://www.designofapproxalgs.com/download.php

章節概要

本書按演算法技術而不是按問題來組織。第1章用多種技術處理同一個問題；第一部分（第1至8章）每種技術一章，作介紹；第二部分（第9至15章）按相同順序回到各項技術，討論要求更高的應用。第16、17章和兩個附錄收尾。各章以習題和指向文獻的章末註記結束。

第1章：近似演算法導論

說明為什麼要研究近似演算法，定義效能保證和近似方案，並指出有些問題根本不存在好的近似。隨後用五種方式處理集合覆蓋問題：線性規劃的確定性捨入、對偶解的捨入、原始-對偶方法、貪心演算法和隨機捨入。作者在這裡引入線性規劃的術語。

第2章：貪心演算法與局部搜尋

對比貪心演算法與局部搜尋演算法。涉及的問題有：單機帶截止時間的排程、k-中心問題（並有硬度結果，說明因子小於2就意味著 P = NP）、相同平行機上的排程、度量旅行推銷員問題（最近鄰加入、雙樹和 Christofides 演算法）、銀行帳戶浮游額最大化、最小度生成樹以及邊著色。

第3章：資料捨入與動態規劃

對捨入後的輸入使用動態規劃，得到背包問題、相同平行機排程和裝箱問題的近似方案。

第4章：線性規劃的確定性捨入

對分數解做確定性捨入。應用包括單機上（加權）完工時間之和的最小化、帶獎勵的 Steiner 樹問題、無容量設施選址和裝箱。有一節說明如何用橢球法在多項式時間內求解大型線性規劃。

第5章：線性規劃的隨機抽樣與隨機捨入

從 MAX SAT 和 MAX CUT 的簡單隨機演算法開始，講解去隨機化、有偏硬幣和隨機捨入，然後是非線性捨入和從兩個解中取較優者。其他應用有帶獎勵的 Steiner 樹、設施選址、帶釋放時間的單機排程、Chernoff 界和整數多商品流，以及稠密3-可著色圖的著色。

第6章：半定規劃的隨機捨入

介紹半定規劃和用隨機超平面進行捨入。應用有尋找大割、近似二次規劃、相關聚類和3-可著色圖的著色。

第7章：原始-對偶方法

透過一系列問題所體現的原則來展開該方法：回顧集合覆蓋問題、反饋頂點集、最短 s-t 路徑、廣義 Steiner 樹問題、最小背包問題，然後是用拉格朗日鬆弛處理的無容量設施選址和 k-中位問題。

第8章：割與度量

透過度量和線性規劃處理割問題：多路割（基於最小割的演算法和線性規劃捨入演算法）、多割、平衡割、用樹度量對度量作機率近似（以 buy-at-bulk 網路設計為應用），以及用於線性排列的擴張度量。

第9–10章：貪心與局部搜尋的更多應用；資料捨入與動態規劃的更多應用

第9章回到最小度生成樹的局部搜尋，得到與最優值相差不超過1的結果，並發展設施選址和 k-中位問題的局部搜尋與貪心演算法。第10章給出歐氏旅行推銷員問題（對平面作遞迴劃分並做動態規劃）和平面圖最大獨立集的近似方案。

第11–12章：線性規劃確定性捨入的更多應用；隨機抽樣與隨機捨入的更多應用

第11章講廣義指派問題、最小費用度數受限生成樹，以及基於基本可行解的迭代捨入與可生存網路設計。第12章用組合的隨機演算法再次回到設施選址，然後是單源租或買問題、Steiner 樹問題，以及在稠密圖中尋找大割。

第13–15章：半定規劃、原始-對偶方法、割與度量的更多應用

第13章利用正態分布的性質，把半定規劃的分析擴充套件到二次規劃和3-可著色圖，並加入唯一博弈。第14章給出帶獎勵 Steiner 樹和反饋頂點集的原始-對偶2-近似演算法。第15章講低失真嵌入與最稀疏割、無關路由、割-樹裝箱、最小二分以及均勻最稀疏割問題；其最後一節是全書最長也最複雜的證明。

第16章：證明近似困難性的技術

對困難性證明作較簡短的概述：從 NP 完全問題出發的歸約、保持近似的歸約，以及從機率可檢驗證明、標籤覆蓋和唯一博弈出發的歸約。

第17章：開放問題

一份開放問題清單，從唯一博弈猜想開始，包括度量旅行推銷員問題及其非對稱變體。

附錄 A–B：線性規劃；NP 完全性

對正文用到的線性規劃和複雜性背景作簡要回顧。

核心概念

第1–3章：基礎

• 效能保證：若多項式時間演算法在每個例項上的解都在最優值的 α 倍之內，就稱其為 α-近似演算法。
• 近似方案（PTAS）：對任意固定的 ε 都能達到 1±ε 的一族演算法。
• 局部搜尋與貪心構造：透過局部最優的選擇來構造或改進解。

第4–8章：線性規劃、半定規劃、原始-對偶與度量

• 線性規劃鬆弛與捨入：求解整數規劃的分數版本，再轉化為整數解。
• 隨機捨入與去隨機化：隨機選擇按期望分析，再用條件期望方法消去隨機性。
• 原始-對偶方法：在構造原始解的同時構造可行對偶解，以界定成本。
• 樹度量：以對數量級的損失，用隨機樹逼近一般度量。

第9–17章：擴充套件與極限

• 迭代捨入：反覆求解線性規劃並固定變數，用於度數受限和可生存網路設計。
• 整性間隙：整數規劃與其鬆弛之間的差距，限制了某個形式化所能證明的結果。
• 保持近似的歸約與唯一博弈猜想：證明困難性結果的工具。

評析

優點

• 圍繞技術組織。 每種技術各佔一章，讀者學會何時該用捨入、原始-對偶或局部搜尋；書中反覆回到設施選址、帶獎勵 Steiner 樹、裝箱和最大割，展示更好的工具如何改進結果。
• 透過線性規劃形成統一視角。 前言說明線性規劃和整數規劃處於核心地位，第1章和附錄 A 為計算機背景的讀者補充了術語。
• 為教學而設計。 全書由多次授課的講義發展而來，只收錄足夠簡單、適合課堂的結果，並在每章末附習題和註記。
• 坦率面對困難性。 困難性在第1章和第2章就已出現，第16章和開放問題一章說明哪些結果無法改進。

侷限

• 先修要求實實在在。 前言假定讀者上過演算法課，熟悉證明、基本機率，並略知 NP 完全性；半定規劃還需要基礎線性代數。據前言，正文中為數不多的 NP 完全性歸約可以略過。
• 困難性只是概述。 作者說，僅這一主題就足以另寫一本書，所以第16章很簡短。
• 部分內容已顯陳舊。 開放問題一章反映的是2010年的領域狀況，並提到已宣布但尚未發表的結果。
• 第二部分內容密集。 第二部分不是入門性的；用前言的話說，第15章中 Arora–Rao–Vazirani 的證明是全書最長也最複雜的。

在課程中的定位

在演算法課程書單中，本書是緊接在 Introduction to Algorithms 之類一般演算法教材之後的研究生專題讀物。Vazirani 的 Approximation Algorithms 是最接近的替代品，同樣是對 NP 難問題技術的細緻闡述；Williamson 和 Shmoys 按技術組織並反覆回到相同的問題，並且據作者自述，對排程和半定規劃著墨更多。

Mitzenmacher 和 Upfal 的 Probability and Computing 是讀機率相關章節（第5、6、12、13章）時有用的參照：它深入展開了 Chernoff 界和機率方法。書單中偏應用的書，如 The Algorithm Design Manual、Algorithms Illuminated 和 Algorithms Unlocked，講的是設計與實現，不能取代本書。

如何使用本書

本書面向剛進入近似演算法領域的研究生和研究人員。初學可按順序讀第一部分：第1章在集合覆蓋上給出全貌，第2、3章除演算法外幾乎不需要其他準備，第4、5、7章發展基於線性規劃的方法。第6章需要線性代數，第8章把線性規劃與度量思想結合起來。

讀完第一部分某項技術後若想看到更強的結果，就讀第二部分對應的章節：第9章和第11.1節是不錯的起點，第16章提供困難性背景。每章至少做幾道習題，並藉助章末註記找到原始論文。

版本與來源

本導讀依據作者網站上的免費電子版（僅電子版），該檔案經劍橋大學出版社許可釋出，是提交給出版社的書稿；印刷版格式不同，並有少量更正。內容基於前言、目錄、各章開頭、結尾章節和附錄。