組合優(yōu)化，作為應(yīng)用數(shù)學(xué)中最年輕而又至關(guān)重要的領(lǐng)域之一，整合了組合數(shù)學(xué)、線性規(guī)劃以及算法理論的方法和技巧。由于它在解決從遠(yuǎn)程通訊到超大規(guī)模集成電路、從產(chǎn)品運(yùn)銷到航班機(jī)組排班等領(lǐng)域內(nèi)困難問題方面的成功，這一領(lǐng)域在過去的十年里取得了巨大的、超乎尋常的發(fā)展。
《組合優(yōu)化》是對(duì)這一數(shù)學(xué)分支的一個(gè)理想介紹，它適用于離散數(shù)學(xué)、計(jì)算機(jī)科學(xué)以及運(yùn)籌學(xué)專業(yè)的本科高年級(jí)學(xué)生和研究生。本書由公認(rèn)的專家團(tuán)隊(duì)撰寫而成，對(duì)經(jīng)典概念和最新結(jié)果都提供了全面而又易懂的講解。主要涉及以下課題：
·網(wǎng)絡(luò)流問題
·最優(yōu)匹配
·多面體的整性
·擬陣
·np-完全性
《組合優(yōu)化》以通暢而連貫的講解、基本和高深概念的清晰解釋、眾多現(xiàn)實(shí)生活中的實(shí)例、以及頗有助益的技巧訓(xùn)練習(xí)題為特征，一定會(huì)成為未來許多年里本領(lǐng)域內(nèi)的標(biāo)準(zhǔn)教科書。
著者簡(jiǎn)介
序言
譯者序
第一章 問題和算法
1.1 兩個(gè)問題
1.2 度量運(yùn)行時(shí)間
第二章 最優(yōu)樹和最優(yōu)路
2.1 最小生成樹
2.2 最短路
第三章 最大流問題
3.1 網(wǎng)絡(luò)流問題
3.2 最大流問題
3.3 最大流和最小割的應(yīng)用
3.4 壓入重標(biāo)記最大流算法
3.5 無向圖中的最小割
著者簡(jiǎn)介
序言
譯者序
第一章 問題和算法
1.1 兩個(gè)問題
1.2 度量運(yùn)行時(shí)間
第二章 最優(yōu)樹和最優(yōu)路
2.1 最小生成樹
2.2 最短路
第三章 最大流問題
3.1 網(wǎng)絡(luò)流問題
3.2 最大流問題
3.3 最大流和最小割的應(yīng)用
3.4 壓入重標(biāo)記最大流算法
3.5 無向圖中的最小割
3.5.1 全局最小割(66)
3.5.2 割樹(72)
3.6 多商品流
第四章 最小費(fèi)用流問題
4.1 最小費(fèi)用流問題
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-連接和郵遞員問題
5.5 一般匹配問題
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)化
第七章 旅行售貨商問題
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 問題
9.4 算法和運(yùn)行時(shí)間
9.5 np 類
9.6 np-完全性
9.7 適定性問題的np-完全性
9.8 一些其他問題的np-完全性
9.9 圖靈機(jī)
附錄a 線性規(guī)劃
參考文獻(xiàn)
名詞索引
書單推薦
