近似算法的設計與分析

《近似算法的設計與分析》是2011年高等教育出版社出版的圖書，作者是堵丁柱、葛可一、胡曉東。本書可作為計算機科學和運籌學專業高年級本科生和研究生的近似算法課程的教材，亦可作為相關研究領域科研人員的參考書。

基本介紹

• 書名：近似算法的設計與分析
• 作者：堵丁柱、葛可一、胡曉東
• ISBN：9787040319675
• 出版社：高等教育出版社
• 出版時間：2011 年8月
• 叢書名：算法理論與套用叢書

內容簡介

近似算法是處理難解的組合最佳化問題的一個非常重要和有效的方法。它可以在多項式時間內求得問題的一個解，並使其目標函式值與最優解的目標函式值之比不超過一個常數。本書將通過大量具有代表性的組合最佳化問題，介紹近似算法設計和分析中的三種主要方法：貪婪算法、限制方法和鬆弛方法；所討論的問題來源於不同的研究和套用領域，其中包括通信網路設計，光纖網路，無線自組織網路和感測器網路，生物信息學，社會網路，工業工程和信息管理系統等。

此外，本書還將介紹有關組合最佳化問題不可近似性的一些基本結果。本書的每一章後面都配有相關內容的習題和歷史註記。

圖書目錄

第一章 引言

1.1 “芝麻，開門!”

1.2 近似算法的設計技巧

1.3 啟發式算法與近似算法

1.4 計算複雜性的術語

1.5 np-完全問題

1.6 性能比

習題

歷史註記

第二章 貪婪策略

2.1 獨立系統

2.2 擬陣

2.3 權函式的四邊形條件

2.4 次模勢函式

2.5 套用

2.6 非次模勢函式

習題

歷史註記

第三章 限制

.3.1 斯坦納樹和生成樹

3.2 k-限制斯坦納樹

3.3 貪婪k-限制斯坦納樹

3.4 最小生成樹的套用

3.5 種系進化樹同步

習題

歷史註記

第四章 劃分

4.1 劃分與移位

4.2 邊界區域

4.3 多層劃分

4.4 雙重劃分

4.5 樹劃分

習題

歷史註記

第五章 斷切

5.1 矩形劃分

5.2 l-斷切

5.3 m-斷切

5.4 接口

5.5 四叉樹劃分與補綴

5.6 兩階段接口

習題

歷史註記

第六章 鬆弛

6.1 有向哈密頓圈和超串

6.2 兩階段貪婪近似算法

6.3 單位圓盤圖上連通控制集

6.4 有向圖中的強連通控制集

6.5 光纖網路中的多播路由

6.6 關於鬆弛與限制的附記

習題

歷史註記

第七章 線性規劃

7.1 基本性質

7.2 單純形法

7.3 組合舍人

7.4 管輸舍人

7.5 疊代舍人

7.6 隨機舍人

習題

歷史註記

第八章 原始對偶方案與局部比值法

8.1 對偶理論和原始對偶方案

8.2 廣義覆蓋

8.3 網路設計

8.4 局部比值法

8.5 再論等價性

習題

歷史註記

第九章 半定規劃

9.1 譜面體

9.2 半定規劃

9.3 超平面舍人

9.4 旋轉向量

9.5 多元正交舍人

習題

歷史註記

第十章 不可近似性

10.1 具有間隙的多一歸約

10.2 間隙放大與保持

10.3 apx-完全性

10.4 機率可驗證明定理

10.5 (ρin n)-不可近似性

10.6 nc-不可近似性

習題

歷史註記

參考文獻

名詞索引(漢英對照)