Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics Book 21) 6th Edition by Bernhard Korte (PDF)

Description

This comprehensive textbook on combinatorial optimization places special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. It is based on numerous courses on combinatorial optimization and specialized topics, mostly at graduate level. This book reviews the fundamentals, covers the classical topics (paths, flows, matching, matroids, NP-completeness, approximation algorithms) in detail, and proceeds to advanced and recent topics, some of which have not appeared in a textbook before. Throughout, it contains complete but concise proofs, and also provides numerous exercises and references. This sixth edition has again been updated, revised, and significantly extended. Among other additions, there are new sections on shallow-light trees, submodular function maximization, smoothed analysis of the knapsack problem, the (ln 4+ɛ)-approximation for Steiner trees, and the VPN theorem. Thus, this book continues to represent the state of the art of combinatorial optimization.

User’s Reviews

Reviews from Amazon users which were colected at the time this book was published on the website:

⭐17 11/3に注文して，到着が4/10。船便か？初版が出たきりの専門書が多い中，第6版になる。ここからネタをもらったこともあるし，まちがいなく好い本なものの，以下の理由で星一つ減，かな。施設配置問題とかは定義を見ただけで気絶するので，シンプルなナップサック問題（17章）の感想。今版で追加された17.5節をざっと眺めて，なんか，ばたばたしてる印象を受ける。例へばp.481，せっかくw(S), c(S)の記法を導入したのに，なぜNemhauser-Ullmannのアルゴリズムの定義（囲みの中）で用ゐないのか。加へて，当該アルゴリズムの中で，While中の最初のIfで，w(S1)=w(S2)の場合が最初の条件に吸収されてまうんで，二番目の条件が生きる為には，最初の条件はw(S1)