《組閤優化》
著者簡介
序言
譯者序
第一章問題和算法 1
x1.1 兩個問題 1
x1.2 度量運行時間 4
第二章最優樹和最優路 9
x2.1 最小生成樹 9
x2.2 最短路 18
第三章最大流問題 35
x3.1 網絡流問題 35
x3.2 最大流問題 35
x3.3 最大流和最小割的應用 43
x3.4 壓入重標記最大流算法 57
x3.5 無嚮圖中的最小割 66
3.5.1全局最小割(66) 3.5.2割樹(72)
x3.6 多商品流 78
第四章最小費用流問題 83
x4.1 最小費用流問題 83
.x4.2 原始最小費用流算法 92
x4.3 對偶最小費用流算法 102
x4.4 對偶尺度放大算法 107
第五章最優匹配 115
x5.1 匹配和交錯路 115
x5.2 最大匹配 122
x5.3 最小權完美匹配 130
x5.4 t-連接和郵遞員問題 148
x5.5 一般匹配問題 162
x5.6 幾何對偶和goemans-williamson 算法 170
第六章多麵體的整性 177
x6.1 凸包 177
x6.2 有界多麵體 181
x6.3 側麵 188
x6.4 整有界多麵體 195
x6.5 全幺模性 197
x6.6 全對偶整性 201
x6.7 割平麵 204
x6.8 分離與優化 212
第七章旅行售貨商問題 217
x7.1 引言 217
x7.2 tsp 的啓發式方法 218
x7.3 下界 228
x7.4 割平麵 236
x7.5 分支定界 242
第八章擬陣 247
x8.1 擬陣及貪婪算法 247
x8.2 擬陣: 性質, 公理, 構造 255
x8.3 擬陣交 260
x8.4 擬陣交的應用 266
x8.5 賦權擬陣交 268
第九章np 和np-完全性 279
x9.1 引言 279
x9.2 字 280
x9.3 問題 281
x9.4 算法和運行時間 282
x9.5 np 類 283
x9.6 np-完全性 285
x9.7 適定性問題的np-完全性 285
x9.8 一些其他問題的np-完全性 287
x9.9 圖靈機 290
附錄a 綫性規劃 293
參考文獻 303
名詞索引 313
· · · · · · (收起)