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

內(nèi)容概要

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

作者簡(jiǎn)介

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

書(shū)籍目錄

第一章 引言
　1.1 “芝麻，開(kāi)門(mén)!”
　1.2 近似算法的設(shè)計(jì)技巧
　1.3 啟發(fā)式算法與近似算法
　1.4 計(jì)算復(fù)雜性的術(shù)語(yǔ)
　1.5 np-完全問(wèn)題
　1.6 性能比
　習(xí)題
　歷史注記
第二章 貪婪策略
　2.1 獨(dú)立系統(tǒng)
　2.2 擬陣
　2.3 權(quán)函數(shù)的四邊形條件
　2.4 次模勢(shì)函數(shù)
　2.5 應(yīng)用
　2.6 非次模勢(shì)函數(shù)
　習(xí)題
　歷史注記
第三章 限制
　3.1 斯坦納樹(shù)和生成樹(shù)
　3.2 k-限制斯坦納樹(shù)
　3.3 貪婪k-限制斯坦納樹(shù)
　3.4 最小生成樹(shù)的應(yīng)用
　3.5 種系進(jìn)化樹(shù)同步
　習(xí)題
　歷史注記
第四章 劃分
　4.1 劃分與移位
　4.2 邊界區(qū)域
　4.3 多層劃分
　4.4 雙重劃分
　4.5 樹(shù)劃分
　習(xí)題
　歷史注記
第五章 斷切
　5.1 矩形劃分
　5.2 l-斷切
　5.3 m-斷切
　5.4 接口
　5.5 四叉樹(shù)劃分與補(bǔ)綴
　5.6 兩階段接口
　習(xí)題
　歷史注記
第六章 松弛
　6.1 有向哈密頓圈和超串
　6.2 兩階段貪婪近似算法
　6.3 單位圓盤(pán)圖上連通控制集
　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í)題
　歷史注記
第八章 原始對(duì)偶方案與局部比值法
　8.1 對(duì)偶理論和原始對(duì)偶方案
　8.2 廣義覆蓋
　8.3 網(wǎng)絡(luò)設(shè)計(jì)
　8.4 局部比值法
　8.5 再論等價(jià)性
　習(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)
名詞索引(漢英對(duì)照)

編輯推薦

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

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

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

---