# Combinatorial Optimization: Theory and Algorithms

Springer Science & Business Media, Nov 4, 2007 - Mathematics - 627 pages

Now fully updated in a third edition, this is a comprehensive textbook on combinatorial optimization. It puts special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. The book contains complete but concise proofs, also for many deep results, some of which have not appeared in print before. Recent topics are covered as well, and numerous references are provided. This third edition contains a new chapter on facility location problems, an area which has been extremely active in the past few years. Furthermore there are several new sections and further material on various topics. New exercises and updates in the bibliography were added.

### What people are saying -Write a review

We haven't found any reviews in the usual places.

### Contents

 Introduction 1 11 Enumeration 2 12 Running Time of Algorithms 5 13 Linear Optimization Problems 8 14 Sorting 9 Exercises 11 References 12 Graphs 13
 bMatchings and TJoins 285 122 Minimum Weight TJoins 289 123 TJoins and TCuts 293 124 The PadbergRao Theorem 296 Exercises 299 References 302 Matroids 304 132 Other Matroid Axioms 309

 22 Trees Circuits and Cuts 17 23 Connectivity 24 24 Eulerian and Bipartite Graphs 30 25 Planarity 33 26 Planar Duality 40 Exercises 43 References 46 Linear Programming 48 31 Polyhedra 50 32 The Simplex Algorithm 54 33 Implementation of the Simplex Algorithm 57 34 Duality 60 35 Convex Hulls and Polytopes 64 Exercises 66 References 68 Linear Programming Algorithms 71 42 Continued Fractions 74 43 Gaussian Elimination 77 44 The Ellipsoid Method 80 45 Khachiyans Theorem 86 46 Separation and Optimization 88 Exercises 95 References 96 Integer Programming 98 51 The Integer Hull of a Polyhedron 101 52 Unimodular Transformations 105 53 Total Dual Integrality 107 54 Totally Unimodular Matrices 110 55 Cutting Planes 115 56 Lagrangean Relaxation 119 Exercises 121 References 125 Spanning Trees and Arborescences 127 62 Minimum Weight Arborescences 133 63 Polyhedral Descriptions 137 64 Packing Spanning Trees and Arborescences 140 Exercises 144 References 147 Shortest Paths 151 71 Shortest Paths From One Source 152 72 Shortest Paths Between All Pairs of Vertices 156 73 Minimum Mean Cycles 159 Exercises 161 References 163 Network Flows 165 81 MaxFlowMinCut Theorem 166 82 Mengers Theorem 170 83 The EdmondsKarp Algorithm 172 84 Blocking Flows and Fujishiges Algorithm 174 85 The GoldbergTarjan Algorithm 176 86 GomoryHu Trees 180 87 The Minimum Capacity of a Cut in an Undirected Graph 186 Exercises 189 References 194 Minimum Cost Flows 198 92 An Optimality Criterion 201 93 Minimum Mean CycleCancelling Algorithm 203 94 Successive Shortest Path Algorithm 207 95 Orlins Algorithm 211 96 The Network Simplex Algorithm 214 97 Flows Over Time 218 Exercises 220 References 224 Maximum Matchings 227 101 Bipartite Matching 228 102 The Tutte Matrix 230 103 Tuttes Theorem 232 104 EarDecompositions of FactorCritical Graphs 235 105 Edmonds Matching Algorithm 241 Exercises 250 References 254 Weighted Matching 257 111 The Assignment Problem 258 112 Outline of the Weighted Matching Algorithm 259 113 Implementation of the Weighted Matching Algorithm 262 114 Postoptimality 276 115 The Matching Polytope 277 Exercises 280 References 282
 133 Duality 313 134 The Greedy Algorithm 317 135 Matroid Intersection 322 136 Matroid Partitioning 327 137 Weighted Matroid Intersection 329 Exercises 332 References 334 Generalizations of Matroids 337 142 Polymatroids 341 143 Minimizing Submodular Functions 345 144 Schrijvers Algorithm 347 145 Symmetric Submodular Functions 351 Exercises 353 References 355 NPCompleteness 359 152 Churchs Thesis 362 153 P and NP 367 154 Cooks Theorem 371 155 Some Basic NPComplete Problems 375 156 The Class coNP 382 157 NPHard Problems 384 Exercises 387 References 391 Approximation Algorithms 393 161 Set Covering 394 162 The MaxCut Problem 399 163 Colouring 405 164 Approximation Schemes 413 165 Maximum Satisfiability 415 166 The PCP Theorem 420 167 LReductions 424 Exercises 430 References 434 The Knapsack Problem 438 172 A Pseudopolynomial Algorithm 442 173 A Fully Polynomial Approximation Scheme 444 Exercises 447 BinPacking 449 182 An Asymptotic Approximation Scheme 455 183 The KarmarkarKarp Algorithm 459 Exercises 462 References 464 Multicommodity Flows and EdgeDisjoint Paths 467 191 Multicommodity Flows 468 192 Algorithms for Multicommodity Flows 471 193 Directed EdgeDisjoint Paths Problem 476 194 Undirected EdgeDisjoint Paths Problem 479 Exercises 485 References 487 Network Design Problems 490 201 Steiner Trees 492 202 The RobinsZelikovsky Algorithm 497 203 Survivable Network Design 502 204 A PrimalDual Approximation Algorithm 505 205 Jains Algorithm 514 Exercises 520 References 522 The Traveling Salesman Problem 527 212 Euclidean TSP 532 213 Local Search 539 214 The Traveling Salesman Polytope 545 215 Lower Bounds 551 216 BranchandBound 553 Exercises 556 References 559 Facility Location 563 222 Rounding Linear Programming Solutions 565 223 PrimalDual Algorithms 567 224 Scaling and Greedy Augmentation 573 225 Bounding the Number of Facilities 576 226 Local Search 579 227 Capacitated Facility Location Problems 585 228 Universal Facility Location 588 Exercises 594 References 596 Notation Index 599 Author Index 602 Subject Index 613 Copyright

### References to this book

 Theoretical Aspects of Local SearchLimited preview - 2007
 Handbook of Approximation Algorithms and MetaheuristicsTeofilo F. GonzalezLimited preview - 2007
All Book Search results &raquo;