近似算法的設(shè)計與分析

內(nèi)容概要

　　近似算法是處理難解的組合優(yōu)化問題的一個非常重要和有效的方法。它可以在多項(xiàng)式時間內(nèi)求得問題的一個解，并使其目標(biāo)函數(shù)值與最優(yōu)解的目標(biāo)函數(shù)值之比不超過一個常數(shù)。本書將通過大量具有代表性的組合優(yōu)化問題，介紹近似算法設(shè)計和分析中的三種主要方法：貪婪算法、限制方法和松弛方法；所討論的問題來源于不同的研究和應(yīng)用領(lǐng)域，其中包括通信網(wǎng)絡(luò)設(shè)計，光纖網(wǎng)絡(luò)，無線自組織網(wǎng)絡(luò)和傳感器網(wǎng)絡(luò)，生物信息學(xué)，社會網(wǎng)絡(luò)，工業(yè)工程和信息管理系統(tǒng)等。此外，本書還將介紹有關(guān)組合優(yōu)化問題不可近似性的一些基本結(jié)果。本書的每一章后面都配有相關(guān)內(nèi)容的習(xí)題和歷史注記。
　　《近似算法的設(shè)計與分析》可作為計算機(jī)科學(xué)和運(yùn)籌學(xué)專業(yè)高年級本科生和研究生的近似算法課程的教材，亦可作為相關(guān)研究領(lǐng)域科研人員的參考書。

作者簡介

　　　堵丁柱，1948年生。中國科學(xué)院應(yīng)用數(shù)學(xué)研究所運(yùn)籌學(xué)碩士（1981），美國加利福尼亞大學(xué)圣巴巴拉分校數(shù)學(xué)博士（1985），美國伯克利數(shù)學(xué)科學(xué)研究所博士后（1985－1986），美國麻省理工學(xué)院助理教授（1986－1987），美國普林斯頓大學(xué)訪問學(xué)者（1990－1991）。曾任美國明尼蘇達(dá)大學(xué)計算機(jī)科學(xué)系教授，中國科學(xué)院應(yīng)用數(shù)學(xué)研究所研究員，美國自然科學(xué)基金會項(xiàng)目主任，西安交通大學(xué)理學(xué)院院長?，F(xiàn)任美國得克薩斯大學(xué)達(dá)拉斯分校計算機(jī)系教授，西安交通大學(xué)理學(xué)院名譽(yù)院長和高麗大學(xué)世界級大學(xué)教授。

書籍目錄

第一章 引言
　1.1 “芝麻，開門!”
　1.2 近似算法的設(shè)計技巧
　1.3 啟發(fā)式算法與近似算法
　1.4 計算復(fù)雜性的術(shù)語
　1.5 np-完全問題
　1.6 性能比
　習(xí)題
　歷史注記
第二章 貪婪策略
　2.1 獨(dú)立系統(tǒng)
　2.2 擬陣
　2.3 權(quán)函數(shù)的四邊形條件
　2.4 次模勢函數(shù)
　2.5 應(yīng)用
　2.6 非次模勢函數(shù)
　習(xí)題
　歷史注記
第三章 限制
　3.1 斯坦納樹和生成樹
　3.2 k-限制斯坦納樹
　3.3 貪婪k-限制斯坦納樹
　3.4 最小生成樹的應(yīng)用
　3.5 種系進(jìn)化樹同步
　習(xí)題
　歷史注記
第四章 劃分
　4.1 劃分與移位
　4.2 邊界區(qū)域
　4.3 多層劃分
　4.4 雙重劃分
　4.5 樹劃分
　習(xí)題
　歷史注記
第五章 斷切
　5.1 矩形劃分
　5.2 l-斷切
　5.3 m-斷切
　5.4 接口
　5.5 四叉樹劃分與補(bǔ)綴
　5.6 兩階段接口
　習(xí)題
　歷史注記
第六章 松弛
　6.1 有向哈密頓圈和超串
　6.2 兩階段貪婪近似算法
　6.3 單位圓盤圖上連通控制集
　6.4 有向圖中的強(qiáng)連通控制集
　6.5 光纖網(wǎng)絡(luò)中的多播路由
　6.6 關(guān)于松弛與限制的附記
　習(xí)題
　歷史注記
第七章 線性規(guī)劃
　7.1 基本性質(zhì)
　7.2 單純形法
　7.3 組合舍人
　7.4 管輸舍人
　7.5 迭代舍人
　7.6 隨機(jī)舍人
　習(xí)題
　歷史注記
第八章 原始對偶方案與局部比值法
　8.1 對偶理論和原始對偶方案
　8.2 廣義覆蓋
　8.3 網(wǎng)絡(luò)設(shè)計
　8.4 局部比值法
　8.5 再論等價性
　習(xí)題
　歷史注記
第九章 半定規(guī)劃
　9.1 譜面體
　9.2 半定規(guī)劃
　9.3 超平面舍人
　9.4 旋轉(zhuǎn)向量
　9.5 多元正交舍人
　習(xí)題
　歷史注記
第十章 不可近似性
　10.1 具有間隙的多一歸約
　10.2 間隙放大與保持
　10.3 apx-完全性
　10.4 概率可驗(yàn)證明定理
　10.5 (ρin n)-不可近似性
　10.6 nc-不可近似性
　習(xí)題
歷史注記
參考文獻(xiàn)
名詞索引(漢英對照)

編輯推薦

　　近似算法是處理難解的組合優(yōu)化問題的一個非常重要和有效的方法。它可以在多項(xiàng)式時間內(nèi)求得問題的一個解，并使其目標(biāo)函數(shù)值與最優(yōu)解的目標(biāo)函數(shù)值之比不超過一個常數(shù)。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    近似算法的設(shè)計與分析 PDF格式下載

---