近似演算法

引用

Vazirani, V. V. (2001). Approximation Algorithms (1st ed.). Springer. (Corrected second printing 2003; softcover reprint 2010.)

章節概要

全書共三十章，分為三部分，另有兩個附錄。幾乎每一章都圍繞一個問題展開，章末附有習題和註記，正文篇幅很短。

第1章：Introduction（引言）

提出近似保證的基本思想，並以頂點覆蓋為例說明如何通過為最優值（OPT）找下界來完成分析。本章還討論近似保證能否改進，並引入“良刻畫問題”（well-characterized problems）與極小—極大關係。

第一部分，第2–4章：集合覆蓋；Steiner 樹與 TSP；多路割與 k-割

集合覆蓋用貪心演算法和分層（layering）兩種方法處理，並應用到最短超串問題。隨後是 Steiner 樹與度量 TSP，包括簡單的 2 倍演算法以及將 TSP 改進到 3/2 的演算法，再之後是多路割與最小 k-割問題。

第一部分，第5–7章：k-中心；反饋頂點集；最短超串

k-中心問題用引數化剪枝處理，並包含加權版本。反饋頂點集使用圈數加權圖與分層。最短超串先給出 4 倍演算法，再改進到 3 倍。

第一部分，第8–11章：背包；裝箱；最小完工時間排程；歐氏 TSP

這幾章圍繞近似方案展開。背包問題包括偽多項式時間演算法、FPTAS，並討論強 NP 困難性。裝箱得到漸近 PTAS，完工時間排程得到 2 倍演算法和 PTAS，歐氏 TSP 則先給出演算法，再證明其正確性。

第二部分，第12–15章：LP 對偶與集合覆蓋

第12章介紹 LP 對偶、極小—極大關係、本部分的兩種設計技術（舍入與原始—對偶模式）以及整數性間隙。第13–15章三次回到集合覆蓋：用對偶擬合分析貪心演算法、舍入（簡單舍入與隨機舍入，並涉及頂點覆蓋的半整數性），以及原始—對偶模式。

第二部分，第16–21章：最大可滿足性到最稀疏割

最大可滿足性通過去隨機化和 LP 舍入處理，得到 3/4 倍演算法。不相關並行機排程使用極點解的性質。第18–21章依次講樹上的多割、多路割、一般圖上的多割和最稀疏割，其中最稀疏割藉助度量、割填充和低失真嵌入。

第二部分，第22–26章：Steiner 森林到半定規劃

Steiner 森林使用帶同步的原始—對偶模式，Steiner 網路使用迭代舍入。隨後是設施選址和 k-中位問題，後者包含一種拉格朗日鬆弛技術。第26章介紹半定規劃，並對 MAX-2SAT 應用隨機舍入。

第三部分，第27–30章：其他主題

格中的最短向量（第27章）、兩個計數問題（DNF 解的計數與網路可靠性，第28章）、以 PCP 定理為基礎的近似難度，並以集合覆蓋的難度結果為高潮（第29章），以及一份開放問題清單（第30章）。附錄 A 為演算法設計者概述複雜性理論，附錄 B 介紹基本機率論。

核心概念

第1–11章

• 為 OPT 找下界：近似比的證明，是把演算法輸出與一個容易計算的最優值下界相比較。
• 分層與引數化剪枝：用於集合覆蓋、反饋頂點集和 k-中心的兩種組合技術。
• PTAS 與 FPTAS：保證可以任意接近 1 的近似方案；背包一章討論了 FPTAS 何時才可能存在。

第12–26章

• LP 對偶與整數性間隙：連線線性規劃與其對偶的定理，以及限制基於某個鬆弛的任何分析的比值。
• 對偶擬合、舍入、原始—對偶模式：把 LP 鬆弛變成帶保證的演算法的三種方式。
• 迭代舍入與半定鬆弛：用於 Steiner 網路和 MAX-2SAT 的更復雜的舍入方法。

第27–30章

• 間隙歸約與 PCP 定理：近似難度結果背後的工具。
• 近似計數：近似解的個數，而不是對解做最佳化。

評析

優點

• 章節短小，每章圍繞一個問題。 前言說明各章力求簡短，往往只給出核心結果，推廣內容放入習題。因此很適合一次讀一章。
• 習題與提示。 幾乎每章都有習題和註記，前言還說明部分習題附有提示。
• 技術脈絡體現在結構中。 第二部分按技術組織；集合覆蓋依次用貪心、對偶擬合、舍入和原始—對偶方法重訪，並在第29章給出與之匹配的難度結果。把同一個問題放在多種視角下觀察，對教學很有幫助。
• 背景知識自足。 附錄涵蓋複雜性理論與機率，LP、半定規劃和格分別在第12、26、27章引入。
• 書評者的評價。 Mark Jerrum（Mathematical Reviews，2002）稱其可能是第一本對該主題作廣泛而系統覆蓋的教材，並稱贊其習題豐富。Viggo Kann（Zentralblatt MATH，2003）認為書中的結果往往比原始論文更容易理解；Csanád Imreh（Acta Scientiarum Mathematicarum，2002）認為它既可用於研究生課程，也適合研究人員。

侷限

• 2001 年的快照。 作者寫明本書呈現的是撰寫時的理論狀況，並預期這一圖景會改變；開放問題清單也被描述為圍繞當時的熱點問題。
• 第一部分有意保持多樣。 前言承認，由於沒有嚴格歸類技術，組合演算法部分可能顯得不夠連貫。想要按技術講授的讀者會覺得第二部分更有系統性。
• 部分證明需要接受。 第29章假定 PCP 定理成立，前言說明該定理目前沒有簡單證明；書中也不涉及用於計數的馬爾可夫鏈蒙特卡羅方法。
• 內容超出一門課。 前言說明內容量超過一學期課程的兩倍，因此讀者需要自己選擇路線。

在課程中的定位

在本課程書單中，Vazirani 是一本專門性的教材。Introduction to Algorithms（Cormen、Leiserson、Rivest 和 Stein）是通用參考書；其第35章是近似演算法一章，第34章講 NP 完全性，而這正是 Vazirani 所假定的基礎。Skiena 的 The Algorithm Design Manual 是識別並解決演算法問題的實用指南，近似演算法是其中的方法之一。Roughgarden 的 Algorithms Illuminated 與 Cormen 的 Algorithms Unlocked 是更平緩的演算法入門讀物，適合尚未準備好讀研究生教材的讀者。

最接近的對照是 Williamson 和 Shmoys 的 The Design of Approximation Algorithms，同一主題的研究生教材，其頁面介紹說內容從貪心方法一直到半定規劃，並討論理論極限。兩本書覆蓋的核心內容相近；Vazirani 的特點是以問題為中心的短章和三部分結構，因此兩書適合對照閱讀。Mitzenmacher 等人的 Probability and Computing 是第14、16、26章中隨機舍入的有益補充。

如何使用本書

本書面向高年級本科生和研究生。前言指出，修過本科演算法課並學過 NP 完全性理論，對大多數章節已足夠；附錄 A 和 B 可以幫助複習複雜性與機率。

較合理的第一遍路線是：先讀第1章，再讀第一部分的第2、3、5和8–10章（前言說明各部分章節大致按難度遞增排列）。接著讀第12–15章，它們在同一個熟悉的問題上引入 LP 對偶和三種 LP 技術，然後讀第16、17和24章。第18–23、25、26章可作為可選的第二遍，適合想學習割、網路設計、聚類和半定方法的讀者。想了解難度一面的讀者，可在讀過附錄 A 後閱讀第29章。對於一般的演算法課程，前言只推薦把第一、二部分的前幾章作為補充讀物。

請做習題：推廣和相關結果都放在習題裡，章末註記則給出進一步閱讀的參考文獻。