| Preface | iii |
Chapter 1 | Introduction | 1 |
1. | What is Combinatorial Optimization? | 1 |
2. | Some Representative Optimization Problems | 2 |
3. | When is a Problem Solved? | 4 |
4. | The Criterion of Polynomial Boundedness | 5 |
5. | Some Apparently Nonpolynomial-Bounded Problems | 8 |
6. | Methods of Solution | 10 |
| Comments and References | 12 |
Chapter 2 | Mathematical Preliminaries | 15 |
1. | Mathematical Prerequisites | 15 |
2. | Sets and Relations | 16 |
3. | Graphs and Digraphs | 20 |
4. | Subgraphs, Cliques, Multigraphs | 24 |
5. | Connectivity in Graphs | 26 |
6. | Connectivity in Digraphs | 28 |
7. | Cocycles and Directed Cocycles | 31 |
8. | Planarity and Duality | 32 |
9. | Eulerian and Hamiltonian Graphs | 36 |
10. | Linear Programming Problems | 39 |
11. | The Simplex Method | 43 |
12. | Geometric Interpretation | 48 |
13. | Duality Theory | 53 |
| Comments and References | 58 |
Chapter 3 | Shortest Paths | 59 |
1. | Introduction | 59 |
2. | Some Problem Formulations | 61 |
3. | Bellman's Equations | 65 |
4. | Acyclic Networks | 68 |
5. | Networks with Positive Arcs: Dijkstra's Method | 70 |
6. | Solution by Successive Approximations: Bellman-Ford Method Method | 74 |
7. | Improvements in Efficiency: Yen's Modifications | 76 |
8. | Linear Programming Interpretation and Relaxation Procedures | 77 |
9. | Shortest Paths between all Pairs of Nodes: Matrix Multiplication | 82 |
10. | Floyd-Warshall Method | 86 |
11. | Detection of Negative Cycles | 90 |
12. | Networks with Transit Times | 92 |
13. | The Minimal Cost-to-time Ratio Cycle Problem | 94 |
14. | M Shortest Paths: Dreyfus Method | 98 |
15. | M Shortest Paths without Repeated Nodes | 100 |
| Comments and References | 104 |
Chapter 4 | Network Flows | 109 |
1. | Introduction | 109 |
2. | Maximal Flows | 110 |
3. | Maximal Flow Algorithm | 114 |
4. | Efficiency of the Maximal Flow Algorithm | 116 |
5. | Combinatorial Implications of Max-Flow Min-Cut Theorem | 120 |
6. | Linear Programming Interpretation of Max-Flow Min-Cut Theorem | 123 |
7. | Minimum Cost Flows | 129 |
8. | Networks with Losses and Gains | 134 |
9. | Lower Bounds and Circulations | 138 |
10. | The Out-of-Kilter Method | 142 |
11. | Theoretical Improvement in Efficiency of Out-of-Kilter Method | 157 |
12. | Integrality of Flows and the Unimodular Property | 160 |
13. | Application to Project Scheduling | 165 |
14. | Transhipment and Transportation Problems | 169 |
15. | Multiterminal and Multicommodity Flows | 173 |
| Comments and References | 177 |
Chapter 5 | Bipartite Matching | 182 |
1. | Introduction | 182 |
2. | Problem Reductions and Equivalences | 184 |
3. | Counterparts of Network Flow Theorems | 188 |
4. | Mendelsohn-Dulmage Theorem | 191 |
5. | Cardinality Matching Algorithm | 193 |
6. | A Special Case: Convex Graphs | 196 |
7. | Max-Min Matching | 197 |
8. | The Hungarian Method for Weighted Matching | 201 |
9. | A Special Case: Gilmore-Gomory Matching | 207 |
10. | A Novel Optimization Criterion: Gale-Shapley Matching | 211 |
| Comments and References | 214 |
Chapter 6 | Nonbipartite Matching | 217 |
1. | Introduction | 217 |
2. | Problem Formulations | 218 |
3. | Bidirected Flows | 223 |
4. | Augmenting Paths | 226 |
5. | Trees and Blossoms | 229 |
6. | Cardinality Matching Algorithm | 233 |
7. | Duality Theory | 239 |
8. | Linear Programming Formulation of Weighted Matching Problem | 242 |
9. | An O (n[superscript 4]) Weighted Matching Algorithm | 247 |
10. | An O (n[superscript 3]) Weighted Matching Algorithm | 252 |
11. | The Chinese Postman's Problem | 259 |
| Comments and References | 261 |
Chapter 7 | Matroids and the Greedy Algorithm | 264 |
1. | Introduction | 264 |
2. | Three Apparently Unrelated Optimization Problems | 265 |
3. | Matroid Definitions | 268 |
4. | Matching, Transversal, and Partition Matroids | 271 |
5. | Matroid Axiomatics | 273 |
6. | The Matroid Greedy Algorithm | 275 |
7. | Applications of the Greedy Algorithm | 278 |
8. | Matroid Duality | 280 |
9. | Variations of the Greedy Algorithm | 283 |
10. | Prim Spanning Tree Algorithm | 285 |
11. | An Application: Flow Network Synthesis | 286 |
12. | The Steiner Problem and Other Dilemmas | 290 |
| Comments and References | 296 |
Chapter 8 | Matroid Intersections | 300 |
1. | Introduction | 300 |
2. | Problem Formulations | 301 |
3. | Augmenting Sequences and Border Graphs | 306 |
4. | Cardinality Intersection Algorithm | 313 |
5. | Duality Theory | 315 |
6. | Generalized Mendelsohn-Dulmage Theorem, Matroid Sums and Matroid Partitions | 317 |
7. | Matroid Partitioning Algorithm | 320 |
8. | The Shannon Switching Game | 324 |
9. | Weighted Augmenting Sequences | 326 |
10. | Primal Weighted Intersection Algorithm | 332 |
11. | Matroid Polyhedra | 334 |
12. | Explanation of Primal-Dual Method | 339 |
13. | Primal-Dual Weighted Intersection Algorithm | 345 |
14. | A Special Case: Directed Spanning Trees | 348 |
| Comments and References | 352 |
Chapter 9 | The Matroid Parity Problem | 356 |
1. | Introduction | 356 |
2. | Problem Formulations | 358 |
3. | Augmenting Sequences | 363 |
4. | Generalizations | 364 |
| Comments and References | 367 |
| Author Index | 368 |
| Subject Index | 371 |