設(shè)施選址問題的近似算法

前言

　　設(shè)施選址問題在運籌學(xué)、計算機(jī)科學(xué)和管理科學(xué)領(lǐng)域受到了廣泛關(guān)注，最近十幾年來，人們在設(shè)施選址問題的近似算法領(lǐng)域取得了非常豐富的研究成果?！　”緯?章介紹問題模型和結(jié)果，第2～4章分別介紹經(jīng)典的無容量限制的設(shè)施選址問題的線性規(guī)劃舍入算法、原始對偶算法和局部搜索算法.第5～9章介紹設(shè)施選址問題的各種變形。書中3.5，5.1，5.2，6.3～6.5，7.1，7.2，8.2，8.3，9.1～9.4節(jié)是作者與合作者近年來的研究成果[4，20，21，45，52～54，61，64，71，72，75～78]，其他章節(jié)取材于文獻(xiàn)[1，6，9，13，17，30，37～39，44，47，50，56，63，67]?！　”緯鴥?nèi)容曾在北京工業(yè)大學(xué)運籌學(xué)專業(yè)的近似算法研究生課程和討論班中講授過，感謝作者的研究生吳晨晨、王鳳敏、王星、萬瑋、余讓慧以及博士后合作者任建峰錄入部分內(nèi)容并校對初稿，其中前兩位學(xué)生付出了很多時間和精力，書中所有的插圖由吳晨晨完成，名詞索引由王鳳敏完成。感謝朋友和同事陳旭瑾、杜東雷、李改弟、蓋玲、舒嘉、邢文訓(xùn)、薛毅、張國川、張海斌、朱文興等對本書的初稿提出的寶貴建議和修改意見?！　「兄x中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院的韓繼業(yè)教授、袁亞湘教授、胡曉東教授、斯坦福大學(xué)的葉蔭宇教授、明尼蘇達(dá)大學(xué)的張樹中教授等多年來給予作者的支持和幫助，感謝北京工業(yè)大學(xué)數(shù)理學(xué)院和紐約大學(xué)商學(xué)院為作者提供的良好科研環(huán)境，感謝科學(xué)出版社責(zé)任編輯為本書的撰寫和編輯提供的幫助。此外，作者要感謝各自的家人對作者工作給予的支持和理解。特別地，在書稿的寫作過程中，本書第一作者徐大川的母親、曲阜師范大學(xué)數(shù)學(xué)系方逸耀副教授生前一直鼓勵其潛心學(xué)術(shù)研究，安心著書，謹(jǐn)以此書獻(xiàn)給她?！　　?/pre>


內(nèi)容概要
　　設(shè)施選址問題是經(jīng)典的NP-難解問題之一，在運籌學(xué)、計算機(jī)科學(xué)和管理科學(xué)中有著廣泛的應(yīng)用?！哆\籌與管理科學(xué)叢書14：設(shè)施選址問題的近似算法》介紹了設(shè)施選址問題及其變形的近似算法。主要內(nèi)容包括：無容量限制的設(shè)施選址問題的線性規(guī)劃舍入算法、無容量限制的設(shè)施選址問題的原始對偶算法、無容量限制的設(shè)施選址問題的局部搜索算法、有容量限制的設(shè)施選址問題、k層設(shè)施選址問題、凹設(shè)施選址問題、不確定設(shè)施選址問題、設(shè)施選址問題的其他變形等。
　　《運籌與管理科學(xué)叢書14：設(shè)施選址問題的近似算法》可作為運籌學(xué)、計算機(jī)科學(xué)、管理科學(xué)和應(yīng)用數(shù)學(xué)專業(yè)的高年級本科生和研究生的教材和參考書，亦可供相關(guān)研究領(lǐng)域科研人員參考。



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









圖書封面






評論、評分、閱讀與下載



還沒讀過(10)
勉強(qiáng)可看(758)
一般般(129)
內(nèi)容豐富(5366)
強(qiáng)力推薦(440)


 


    設(shè)施選址問題的近似算法 PDF格式下載