網絡流算法 Network Flow Algorithms

David P. Williamson 吳向軍 譯

網絡流算法

買這商品的人也買了...

相關主題

商品描述

網絡流理論在理論計算機科學、運籌學和離散數學等學科中均有應用，
可用於貨物運輸建模和計算機視覺圖像分割等眾多問題。
本書主要源於康奈爾大學的網絡流算法課程講義，
包含出版年代較早的經典書籍中未能涵蓋的新研究成果。
本書採用簡潔且統一的視點，討論解決網絡流問題的多種組合算法、多項式算法及其分析，
涵蓋最大流、最小代價流、廣義流、多物流和全局最小割集等，
還介紹了關於計算電流的新研究成果及其在經典問題上的應用。
本書可作為面向研究生的網絡流算法教材，也適合該領域的研究人員參考。

作者簡介

David P. Williamson

 康奈爾大學運籌學和信息工程學院教授，ACM會士，SIAM會士。
他在離散優化方面的研究獲得了多個獎項，包括2000年由美國數學協會和數學規劃協會贊助的Fulkerson獎。
他與David B. Shmoys合著的The Design of Approximation Algorithms
（Cambridge, 2011）獲得了2013年的INFORMS Lanchester獎。
他在多個編委會任職，曾任SIAM Journal on Discrete Mathematics的主編。

---譯者簡介---
吳向軍 
博士，中山大學副教授。
主要研究方向為人工智能和算法設計等，近年來主要從事智能規劃領域的研究和規劃系統的設計與開發。

目錄大綱

譯者序
前言
致謝
第 1 章 預備知識：最短路徑算法 1
1.1 無負權邊：Dijkstra 算法 2
1.2 有負權邊：Bellman-Ford算法 5
1.3 負權迴路的檢測算法 9
練習 16
章節後記 17
第 2 章 最大流算法 19
2.1 最優化條件 21
2.2 應用：汽車共享問題 27
2.3 應用：棒球隊淘汰問題 28
2.4 應用：最密子圖問題 33
2.5 最大改進增廣路徑算法 37
2.6 容量度量算法 40
2.7 最短增廣路徑算法 42
2.8 推送–重標算法 44
練習 54
章節後記 59
第 3 章 全局最小割集算法 61
3.1 Hao-Orlin 算法 62
3.2 MA 序算法 68
3.3 隨機合併算法 72
3.4 Gomory-Hu 樹 76
練習 83
章節後記 85
第 4 章 其他最大流算法 88
4.1 阻塞流算法 88
4.2 單位容量圖的阻塞流 90
4.3 Goldberg-Rao 算法 92
練習 96
章節後記 97
版權聲明 97
第 5 章 最小代價環流算法 99
5.1 最優化條件 101
5.2 Wallacher 算法 104
5.3 最小均值迴路消去算法 109
5.4 容量度量算法 115
5.5 逐次逼近 119
5.6 網絡單純形 124
5.7 應用: 帶時限的最大流問題 126
練習 130
章節後記 136
第 6 章 廣義流算法 139
6.1 最優化條件 141
6.2 Wallacher 式 GAP 消去算法 146
6.3 負代價 GAP 檢測 151
6.4 有損圖、Truemper 算法和收益度量 155
6.5 誤差度量 161
練習 163
章節後記 164
第 7 章 多物流算法 166
7.1 最優化條件 166
7.2 雙物流問題 168
7.3 預備知識：乘權算法 171
7.4 Garg-K.nemann 算法 175
7.5 Awerbuch-Leighton 算法 178
練習 184
章節後記 185
第 8 章 電流算法 187
8.1 最優化條件 187
8.2 無向圖的最大流問題 196
8.3 圖的稀疏化 199
8.4 簡易 Laplacian 求解器 204
練習 210
章節後記 212
版權聲明 213
第 9 章 開放問題 214
參考文獻 216

類似商品