組合優(yōu)化，作為應(yīng)用數(shù)學(xué)中最年輕而又至關(guān)重要的領(lǐng)域之一，整合了組合數(shù)學(xué)、線(xiàn)性規(guī)劃以及算法理論的方法和技巧。由于它在解決從遠(yuǎn)程通訊到超大規(guī)模集成電路、從產(chǎn)品運(yùn)銷(xiāo)到航班機(jī)組排班等領(lǐng)域內(nèi)困難問(wèn)題方面的成功，這一領(lǐng)域在過(guò)去的十年里取得了巨大的、超乎尋常的發(fā)展。
《組合優(yōu)化》是對(duì)這一數(shù)學(xué)分支的一個(gè)理想介紹，它適用于離散數(shù)學(xué)、計(jì)算機(jī)科學(xué)以及運(yùn)籌學(xué)專(zhuān)業(yè)的本科高年級(jí)學(xué)生和研究生。本書(shū)由公認(rèn)的專(zhuān)家團(tuán)隊(duì)撰寫(xiě)而成，對(duì)經(jīng)典概念和最新結(jié)果都提供了全面而又易懂的講解。主要涉及以下課題：
·網(wǎng)絡(luò)流問(wèn)題
·最優(yōu)匹配
·多面體的整性
·擬陣
·np-完全性
《組合優(yōu)化》以通暢而連貫的講解、基本和高深概念的清晰解釋、眾多現(xiàn)實(shí)生活中的實(shí)例、以及頗有助益的技巧訓(xùn)練習(xí)題為特征，一定會(huì)成為未來(lái)許多年里本領(lǐng)域內(nèi)的標(biāo)準(zhǔn)教科書(shū)。
著者簡(jiǎn)介
序言
譯者序
第一章 問(wèn)題和算法
1.1 兩個(gè)問(wèn)題
1.2 度量運(yùn)行時(shí)間
第二章 最優(yōu)樹(shù)和最優(yōu)路
2.1 最小生成樹(shù)
2.2 最短路
第三章 最大流問(wèn)題
3.1 網(wǎng)絡(luò)流問(wèn)題
3.2 最大流問(wèn)題
3.3 最大流和最小割的應(yīng)用
3.4 壓入重標(biāo)記最大流算法
3.5 無(wú)向圖中的最小割
著者簡(jiǎn)介
序言
譯者序
第一章 問(wèn)題和算法
1.1 兩個(gè)問(wèn)題
1.2 度量運(yùn)行時(shí)間
第二章 最優(yōu)樹(shù)和最優(yōu)路
2.1 最小生成樹(shù)
2.2 最短路
第三章 最大流問(wèn)題
3.1 網(wǎng)絡(luò)流問(wèn)題
3.2 最大流問(wèn)題
3.3 最大流和最小割的應(yīng)用
3.4 壓入重標(biāo)記最大流算法
3.5 無(wú)向圖中的最小割
3.5.1 全局最小割(66)
3.5.2 割樹(shù)(72)
3.6 多商品流
第四章 最小費(fèi)用流問(wèn)題
4.1 最小費(fèi)用流問(wèn)題
4.2 原始最小費(fèi)用流算法
4.3 對(duì)偶最小費(fèi)用流算法
4.4 對(duì)偶尺度放大算法
第五章 最優(yōu)匹配
5.1 匹配和交錯(cuò)路
5.2 最大匹配
5.3 最小權(quán)完美匹配
5.4 t-連接和郵遞員問(wèn)題
5.5 一般匹配問(wèn)題
5.6 幾何對(duì)偶和goemans-williamson 算法
第六章 多面體的整性
6.1 凸包
6.2 有界多面體
6.3 側(cè)面
6.4 整有界多面體
6.5 全幺模性
6.6 全對(duì)偶整性
6.7 割平面
6.8 分離與優(yōu)化
第七章 旅行售貨商問(wèn)題
7.1 引言
7.2 tsp 的啟發(fā)式方法
7.3 下界
7.4 割平面
7.5 分支定界
第八章 擬陣
8.1 擬陣及貪婪算法
8.2 擬陣: 性質(zhì), 公理, 構(gòu)造
8.3 擬陣交
8.4 擬陣交的應(yīng)用
8.5 賦權(quán)擬陣交
第九章 np 和np-完全性
9.1 引言
9.2 字
9.3 問(wèn)題
9.4 算法和運(yùn)行時(shí)間
9.5 np 類(lèi)
9.6 np-完全性
9.7 適定性問(wèn)題的np-完全性
9.8 一些其他問(wèn)題的np-完全性
9.9 圖靈機(jī)
附錄a 線(xiàn)性規(guī)劃
參考文獻(xiàn)
名詞索引
書(shū)單推薦
