Combinatorial Optimization by Cook, et al. Table of Contents Preface v 1 Problems and Algorithms 1 1.1 Two Problems 1 1.2 Measuring Running Times 5 2 Optimal Trees and Paths 9 2.1 Minimum Spanning Trees 9 2.2 Shortest Paths 19 3 Maximum Flow Problems 37 3.1 Network Flow Problems 37 3.2 Maximum Flow Problems 38 3.3 Applications of Maximum Flow and Minimu Cut 47 3.4 Push-Relabel Maximum Flow Algorithms 62 3.5 Minimum Cuts in Undirected Graphs 71 3.5.1 Global Minimum Cuts 71 3.5.2 Cut-Trees 78 3.6 Multicommodity Flows 85 4 Minimum-Cost Flow Problems 91 4.1 Minimum-Cost Flow Problems 91 4.2 Primal Minimum-Cost Flow Algorithms 101 4.3 Dual Minimum-Cost Flow Algorithms 112 4.4 Dual Scaling Algorithms 119 5 Optimal Matchings 127 5.1 Matchings and Alternating Paths 127 5.2 Maximum Matching 134 5.3 Minimum-Weight Perfect Matchings 144 5.4 T-Joins and Postman Problems 166 5.5 General Matching Problems 182 5.6 Geometric Duality and the Goemans-Williamson Algorithm 191 6 Integrality of Polyhedra 199 6.1 Convex hulls 199 6.2 Polytopes 203 6.3 Facets 211 6.4 Integral Polytopes 218 6.5 Total Unimodularity 220 6.6 Total Dual Integrality 225 6.7 Cutting Planes 228 6.8 Separation and Optimization 237 7 The Traveling Salesman Problem 241 7.1 Introduction 241 7.2 Heuristics for the TSP 242 7.3 Lower Bounds 252 7.4 Cutting Planes 261 7.5 Branch and Bound 268 8 Matroids 283 8.1 Matroids and the Greedy Algorithm 273 8.2 Matroids: Properties, Axioms, Constructions 282 8.3 Matroid Intersection 287 8.4 Applications of Matroid Intersection 295 8.5 Weighted Matroid Intersection 297 9 NP and NP -Completeness 309 9.1 Introduction 309 9.2 Words 311 9.3 Problems 312 9.4 Algorithms and Running Time 312 9.5 The Class NP 314 9.6 NP -Completeness 315 9.7 NP -Completeness of the satisfiablility Problem 316 9.8 NP -Completeness of Some Other Problems 318 9.9 Turing Machines 321 APPENDIX A Linear Programming 325