內容簡介
《近似算法》《近似算法》系統總結了到本世紀初為止近似算法領域的成果，重點關注近似算法的設計與分析，介紹了這個領域中最重要的問題以及所使用的基本方法和思想。全書分為三部分：第一部分使用不同的算法設計技巧給出了下述最佳化問題的組合近似算法：集合覆蓋、施泰納樹和旅行商、多向割和k-割、k-中心、反饋頂點集、最短超字元串、背包、裝箱問題、最小時間跨度排序、歐幾里得旅行商等。第二部分介紹基於線性規劃的近似算法。第三部分包括四個主題：在一個格中找一個最短向量、計數問題的可近似性、基於PCP定理的近似困難性以及未解決的問題等，這些問題都是近似算法領域中的前沿研究內容。
《近似算法》可作為計算機科學、套用數學、運籌學、信息科學與網路工程、物流與交通運輸、管理科學與工程、生命科學、電子科學與技術等學科專業的研究生及高年級本科生的教學用書，對相關領域的科學研究人員也具有參考價值。
作者簡介
ViiayV.Vazirani，喬治亞理工學院計算學院教授，加州大學伯克利分校McKay客座教授，1979年於麻省理工學院獲得學士學位，1983年於加州大學伯克利分校獲得博士學位。研究興趣包括數理經濟學和對策論中的算法問題、有效精確算法和近似算法的設計、計算複雜性理論等。發表論文120餘篇，出版圖書兩本，獲得多項基金資助。2005年當選為美國計算機協會院士。
目錄
1引言
第一部分組合算法
2集合覆蓋
3施泰納樹和旅行商
4多向割和k-割
5k-中心
6反饋頂點集
7最短超字元串
8背包
9裝箱問題
10最小時間跨度排序
11歐幾里得旅行商
第二部分基於線性規劃的算法
12線性規劃對偶介紹
13用對偶擬合分析集合覆蓋
14捨入套用於集合覆蓋
15對集合覆蓋使用原始對偶模式
16最大可滿足性
17無關平行機排序
18樹的多割和樹的整數多商品流
19多向割
20一般圖的多割
21最稀疏割
22施泰納森林
23施泰納網路
24設施定位
25k-中位點
26半定規劃
第三部分其他主題
27最短向量
28計數問題
29近似困難性
30未解決的問題
附錄
A為算法設計者概述複雜性理論
B機率論的基本事實
參考文獻
問題索引
盤點有關算法書籍
| 算法可以理解為有基本運算及規定的運算順序所構成的完整的解題步驟。或者看成按照要求設計好的有限的確切的計算序列，並且這樣的步驟和序列可以解決一類問題。 |
