設施選址問題的近似算法

內容簡介

設施選址問題是經典的NP-難解問題之一，在運籌學、計算機科學和管理科學中有著廣泛的套用。徐大川等編著的《設施選址問題的近似算法》介紹了設施選址問題及其變形的近似算法。主要內容包括：無容量限制的設施選址問題的線性規劃捨入算法、無容量限制的設施選址問題的原始對偶算法、無容量限制的設施選址問題的局部搜尋算法、有容量限制的設施選址問題、k層設施選址問題、凹設施選址問題、不確定設施選址問題、設施選址問題的其他變形等。

《設施選址問題的近似算法》可作為運籌學、計算機科學、管理科學和套用數學專業的高年級本科生和研究生的教材和參考書，亦可供相關研究領域科研人員參考。

《運籌與管理科學叢書》序
總序
前言
第1章緒論
1.1無容量限制的設施選址問題
1.2設施選址問題的各種變形
第2章無容量限制的設施選址問題的線·性規劃捨入算法
2.1STA算法
2.2Chudak—Shmoys算法
2.2.1簡單的4一近似算法
2.2.2隨機（1+3/e）一近似算法
2.2.3隨機f1+2/e）一近似算法
2.2.41.7336一近似算法
2.3Sviridenko算法
2.4Byrka—Aardal算法
2.5Li算法
第3章無容量限制的設施選址問題的原始對偶算法
3.1Jain—Vazirani算法
3.2Pal—Tardos算法
3.3MMSV算法
3.4JMS算法
3.5MYz算法
第4章無容量限制的設施選址問題的局部搜尋算法
4.1AGKMMP算法
4.2貪婪增廣算法
4.3Guha—Khuller算法
4.3.12.408—近似算法
4.3.2設施費用相同情形
4.3.3近似比下界
4.4Charikar—Guha算法
4.4.1（1+√2+ε）一近似算法
4.4.21.8526—近似算法
4.4.31.728—近似算法
第5章有容量限制的設施選址問題
5.1軟容量限制的設施選址問題
5.2硬容量限制的設施選址問題的局部搜尋算法
5.2.1多交換局部搜尋算法
5.2.2算法分析
5.2.3緊的例子
5.3硬容量限制的設施選址問題的線性規劃捨入算法
第6章k層設施選址問題
6.1問題介紹
6.2線性規劃捨入算法
6.3光滑化的原始對偶算法
6.4組合算法
6.52層設施選址問題
第7章凹設施選址問題
7.1光滑化的原始對偶算法
7.2對偶擬合算法
第8章不確定設施選址問題
8.1兩階段隨機設施選址問題
8.2風險可調的兩階段隨機設施選址問題
8.3動態設施選址問題
第9章設施選址問題的其他變形
9.1次模懲罰設施選址問題
9.2帶服務安置費用的設施選址博弈
9.3極大形式的k層設施選址問題
9.4硬容量限制的k層設施選址問題
參考文獻
索引
《運籌與管理科學叢書》已出版書目

設施選址問題的近似算法

基本介紹

內容簡介

目錄

相關詞條

熱門詞條