Table of Contents
1 Introduction 1
1.1 Enumeration 2
1.2 Running Time of Algorithms 5
1.3 Linear Optimization Problems 8
1.4 Sorting 9
Exercises 11
References 12
2 Graphs 13
2.1 Basic Definitions 13
2.2 Trees, Circuits, and Cuts 17
2.3 Connectivity 24
2.4 Eulerian and Bipartite Graphs 30
2.5 Planarity 33
2.6 Planar Duality 40
Exercises 43
References 46
3 Linear Programming 49
3.1 Polyhedra 50
3.2 The Simplex Algorithm 54
3.3 Implementation of the Simplex Algorithm 57
3.4 Duality 60
3.5 Convex Hulls and Polytopes 64
Exercises 66
References 68
4 Linear Programming Algorithms 71
4.1 Size of Vertices and Faces 71
4.2 Continued Fractions 74
4.3 Gaussian Elimination 77
4.4 The Ellipsoid Method 80
4.5 Khachiyan's Theorem 86
4.6 Separation and Optimization 88
Exercises 95
References 96
5 Integer Programming 99
5.1 The Integer Hull of a Polyhedron 101
5.2 Unimodular Transformations 105
5.3 Total Dual Integrality 107
5.4 Totally Unimodular Matrices 110
5.5 Cutting Planes 115
5.6 Lagrangean Relaxation 119
Exercises 121
References 125
6 Spanning Trees and Arborescences 127
6.1 Minimum Spanning Trees 127
6.2 Minimum Weight Arborescences 133
6.3 Polyhedral Descriptions 137
6.4 Packing Spanning Trees and Arborescences 140
Exercises 144
References 147
7 Shortest Paths 151
7.1 Shortest Paths From One Source 152
7.2 Shortest Paths Between All Pairs of Vertices 156
7.3 Minimum Mean Cycles 159
Exercises 161
References 163
8 Network Flows 165
8.1 Max-How-Min-Cut Theorem 166
8.2 Menger's Theorem 170
8.3 The Edmonds-Karp Algorithm 172
8.4 Blocking Flows and Fujishige's Algorithm 174
8.5 The Goldberg-TarjanAlgorithm 176
8.6 Gomory-Hu Trees 180
8.7 The Minimum Capacity of a Cut in an Undirected Graph 186
Exercises 189
References 194
9 Minimum Cost Flows 199
9.1 Problem Formulation 199
9.2 An Optimality Criterion 201
9.3 Minimum Mean Cycle-Cancelling Algorithm 203
9.4 Successive Shortest Path Algorithm 207
9.5 Orlin's Algorithm 211
9.6 The Network Simplex Algorithm 214
9.7 Flows Over Time 218
Exercises 220
References 224
10 Maximum Matchings 227
10.1 Bipartite Matching 228
10.2 The Tutte Matrix 230
10.3 Tutte's Theorem 232
10.4 Ear-Decompositions of Factor-Critical Graphs 235
10.5 Edmonds' Matching Algorithm 241
Exercises 250
References 254
11 Weighted Matching 257
11.1 The Assignment Problem 258
11.2 Outline of the Weighted Matching Algorithm 259
11.3 Implementation of the Weighted Matching Algorithm 262
11.4 Postoptimality 276
11.5 The Matching Polytope 277
Exercises 280
References 282
12 b-Matchings and T-Joins 285
12.1 b-Matchings 285
12.2 Minimum Weight T-Joins 289
12.3 T-Joins and T-Cuts 293
12.4 The Padberg-Rao Theorem 296
Exercises 299
References 302
13 Matroids 305
13.1 Independence Systems and Matroids 305
13.2 Other Matroid Axioms 309
13.3 Duality 313
13.4 The Greedy Algorithm 317
13.5 Matroid Intersection 322
13.6 Matroid Partitioning 327
13.7 Weighted Matroid Intersection 329
Exercises 332
References 334
14 Generalizations of Matroids 337
14.1 Greedoids 337
14.2 Polymatroids 341
14.3 Minimizing Submodular Functions 345
14.4 Schrijver's Algorithm 347
14.5 Symmetric Submodular Functions 351
Exercises 353
References 355
15 AT-Completeness 359
15.1 Turing Machines 359
15.2 Church's Thesis 362
15.3 P and NP 367
15.4 Cook's Theorem 371
15.5 Some Basic NP-Complete Problems 375
15.6 The Class coNP 382
15.7 NP-Hard Problems 384
Exercises 387
References 391
16 Approximation Algorithms 393
16.1 Set Covering 394
16.2 The Max-Cut Problem 399
16.3 Colouring 405
16.4 Approximation Schemes 413
16.5 Maximum Satisfiability 415
16.6 The PCP Theorem 420
16.7 L-Reductions 424
Exercises 430
References 434
17 The Knapsack Problem 439
17.1 Fractional Knapsack and Weighted Median Problem 439
17.2 A Pseudopolynomial Algorithm 442
17.3 A Fully Polynomial Approximation Scheme 444
Exercises 447
References 447
18 Bin-Packing 449
18.1 Greedy Heuristics 449
18.2 An Asymptotic Approximation Scheme 455
18.3 The Karmarkar-Karp Algorithm 459
Exercises 462
References 464
19 Multicommodity Flows and Edge-Disjoint Paths 467
19.1 Multicommodity Flows 468
19.2 Algorithms for Multicommodity Flows 471
19.3 Directed Edge-Disjoint Paths Problem 476
19.4 Undirected Edge-Disjoint Paths Problem 479
Exercises 485
References 487
20 Network Design Problems 491
20.1 Steiner Trees 492
20.2 The Robins-Zelikovsky Algorithm 497
20.3 Survivable Network Design 502
20.4 A Primal-Dual Approximation Algorithm 505
20.5 Jain's Algorithm 514
Exercises 520
References 522
21 The Traveling Salesman Problem 527
21.1 Approximation Algorithms for the TSP 527
21.2 Euclidean TSP 532
21.3 Local Search 539
21.4 The Traveling Salesman Polytope 545
21.5 Lower Bounds 551
22.5 Branch-and-Bound 553
Exercises 556
References 559
22 Facility Location 563
22.1 The Uncapacitated Facility Location Problem 563
22.2 Rounding Linear Programming Solutions 565
22.3 Primal-Dual Algorithms 567
22.4 Scaling and Greedy Augmentation 573
22.5 Bounding the Number of Facilities 576
22.6 Local Search 579
22.7 Capacitated Facility Location Problems 585
22.8 Universal Facility Location 588
Exercises 594
References 596
Notation Index 599
Author Index 603
Subject Index 613
