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