近似算法的設計與分析簡(jiǎn)介，目錄書(shū)摘
2019-11-08 14:24
來(lái)源：京東
作者：京東
近似算法的設計與分析
暫無(wú)報價(jià)
100+評論
100%好評
編輯推薦: 近似算法是處理難解的組合優(yōu)化問(wèn)題的一個(gè)非常重要和有效的方法。它可以在多項式時(shí)間內求得問(wèn)題的一個(gè)解，并使其目標函數值與*優(yōu)解的目標函數值之比不超過(guò)一個(gè)常數。
內容簡(jiǎn)介: 《近似算法的設計與分析》將通過(guò)大量具有代表性的組合優(yōu)化問(wèn)題，介紹近似算法設計和分析中的三種主要方法：貪婪算法、限制方法和松弛方法；所討論的問(wèn)題來(lái)源于不同的研究和應用領(lǐng)域，其中包括通信網(wǎng)絡(luò )設計，光纖網(wǎng)絡(luò )，無(wú)線(xiàn)自組織網(wǎng)絡(luò )和傳感器網(wǎng)絡(luò )，生物信息學(xué)，社會(huì )網(wǎng)絡(luò )，工業(yè)工程和信息管理系統等。此外，《近似算法的設計與分析》還將介紹有關(guān)組合優(yōu)化問(wèn)題不可近似性的一些基本結果?！督扑惴ǖ脑O計與分析》的每一章后面都配有相關(guān)內容的習題和歷史注記。
《近似算法的設計與分析》可作為計算機科學(xué)和運籌學(xué)專(zhuān)業(yè)高年級本科生和研究生的近似算法課程的教材，亦可作為相關(guān)研究領(lǐng)域科研人員的參考書(shū)。
《近似算法的設計與分析》可作為計算機科學(xué)和運籌學(xué)專(zhuān)業(yè)高年級本科生和研究生的近似算法課程的教材，亦可作為相關(guān)研究領(lǐng)域科研人員的參考書(shū)。
作者簡(jiǎn)介: 堵丁柱，1948年生。中國科學(xué)院應用數學(xué)研究所運籌學(xué)碩士（1981），美國加利福尼亞大學(xué)圣巴巴拉分校數學(xué)博士（1985），美國伯克利數學(xué)科學(xué)研究所博士后（1985－1986），美國麻省理工學(xué)院助理教授（1986－1987），美國普林斯頓大學(xué)訪(fǎng)問(wèn)學(xué)者（1990－1991）。曾任美國明尼蘇達大學(xué)計算機科學(xué)系教授，中國科學(xué)院應用數學(xué)研究所研究員，美國自然科學(xué)基金會(huì )項目主任，西安交通大學(xué)理學(xué)院院長(cháng)?，F任美國得克薩斯大學(xué)達拉斯分校計算機系教授，西安交通大學(xué)理學(xué)院名譽(yù)院長(cháng)和高麗大學(xué)世界級大學(xué)教授。
目錄:第一章 引言
1.1 “芝麻，開(kāi)門(mén)！”
1.2 近似算法的設計技巧
1.3 啟發(fā)式算法與近似算法
1.4 計算復雜性的術(shù)語(yǔ)
1.5 np-完全問(wèn)題
1.6 性能比
習題
歷史注記
第二章 貪婪策略
2.1 獨立系統
2.2 擬陣
2.3 權函數的四邊形條件
2.4 次模勢函數
2.5 應用
2.6 非次模勢函數
習題
歷史注記
第三章 限制
3.1 斯坦納樹(shù)和生成樹(shù)
3.2 k-限制斯坦納樹(shù)
3.3 貪婪k-限制斯坦納樹(shù)
3.4 最小生成樹(shù)的應用
3.5 種系進(jìn)化樹(shù)同步
習題
歷史注記
第四章 劃分
4.1 劃分與移位
4.2 邊界區域
4.3 多層劃分
4.4 雙重劃分
4.5 樹(shù)劃分
習題
歷史注記
第五章 斷切
5.1 矩形劃分
5.2 l-斷切
5.3 m-斷切
5.4 接口
5.5 四叉樹(shù)劃分與補綴
5.6 兩階段接口
習題
歷史注記
第六章 松弛
6.1 有向哈密頓圈和超串
6.2 兩階段貪婪近似算法
6.3 單位圓盤(pán)圖上連通控制集
6.4 有向圖中的強連通控制集
6.5 光纖網(wǎng)絡(luò )中的多播路由
6.6 關(guān)于松弛與限制的附記
習題
歷史注記
第七章 線(xiàn)性規劃
7.1 基本性質(zhì)
7.2 單純形法
7.3 組合舍人
7.4 管輸舍人
7.5 迭代舍人
7.6 隨機舍人
習題
歷史注記
第八章 原始對偶方案與局部比值法
8.1 對偶理論和原始對偶方案
8.2 廣義覆蓋
8.3 網(wǎng)絡(luò )設計
8.4 局部比值法
8.5 再論等價(jià)性
習題
歷史注記
第九章 半定規劃
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-不可近似性
習題
歷史注記
參考文獻
名詞索引（漢英對照）
1.1 “芝麻，開(kāi)門(mén)！”
1.2 近似算法的設計技巧
1.3 啟發(fā)式算法與近似算法
1.4 計算復雜性的術(shù)語(yǔ)
1.5 np-完全問(wèn)題
1.6 性能比
習題
歷史注記
第二章 貪婪策略
2.1 獨立系統
2.2 擬陣
2.3 權函數的四邊形條件
2.4 次模勢函數
2.5 應用
2.6 非次模勢函數
習題
歷史注記
第三章 限制
3.1 斯坦納樹(shù)和生成樹(shù)
3.2 k-限制斯坦納樹(shù)
3.3 貪婪k-限制斯坦納樹(shù)
3.4 最小生成樹(shù)的應用
3.5 種系進(jìn)化樹(shù)同步
習題
歷史注記
第四章 劃分
4.1 劃分與移位
4.2 邊界區域
4.3 多層劃分
4.4 雙重劃分
4.5 樹(shù)劃分
習題
歷史注記
第五章 斷切
5.1 矩形劃分
5.2 l-斷切
5.3 m-斷切
5.4 接口
5.5 四叉樹(shù)劃分與補綴
5.6 兩階段接口
習題
歷史注記
第六章 松弛
6.1 有向哈密頓圈和超串
6.2 兩階段貪婪近似算法
6.3 單位圓盤(pán)圖上連通控制集
6.4 有向圖中的強連通控制集
6.5 光纖網(wǎng)絡(luò )中的多播路由
6.6 關(guān)于松弛與限制的附記
習題
歷史注記
第七章 線(xiàn)性規劃
7.1 基本性質(zhì)
7.2 單純形法
7.3 組合舍人
7.4 管輸舍人
7.5 迭代舍人
7.6 隨機舍人
習題
歷史注記
第八章 原始對偶方案與局部比值法
8.1 對偶理論和原始對偶方案
8.2 廣義覆蓋
8.3 網(wǎng)絡(luò )設計
8.4 局部比值法
8.5 再論等價(jià)性
習題
歷史注記
第九章 半定規劃
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-不可近似性
習題
歷史注記
參考文獻
名詞索引（漢英對照）
京公網(wǎng)安備 11000002000088號
