P1: IML/SPH P2: IML/SPH QC: IML/SPH T1: IML
CB636-FM CB636-Lee [Link] December 11, 2003 16:30 Char Count= 0
Contents
Preface page xiii
Introduction 1
0 Polytopes and Linear Programming 9
0.1 Finite Systems of Linear Inequalities 9
0.2 Linear-Programming Duality 14
0.3 Basic Solutions and the Primal Simplex Method 21
0.4 Sensitivity Analysis 27
0.5 Polytopes 29
0.6 Lagrangian Relaxation 35
0.7 The Dual Simplex Method 40
0.8 Totally Unimodular Matrices, Graphs, and Digraphs 41
0.9 Further Study 47
1 Matroids and the Greedy Algorithm 49
1.1 Independence Axioms and Examples of Matroids 49
1.2 Circuit Properties 51
1.3 Representations 53
1.4 The Greedy Algorithm 56
1.5 Rank Properties 60
1.6 Duality 63
1.7 The Matroid Polytope 66
1.8 Further Study 73
2 Minimum-Weight Dipaths 75
2.1 No Negative-Weight Cycles 76
2.2 All-Pairs Minimum-Weight Dipaths 78
ix
Cambridge
Published online by Cambridge Books
University Press Online © Cambridge University Press, 2010
P1: IML/SPH P2: IML/SPH QC: IML/SPH T1: IML
CB636-FM CB636-Lee [Link] December 11, 2003 16:30 Char Count= 0
x Contents
2.3 Nonnegative Weights 78
2.4 No Dicycles and Knapsack Programs 81
2.5 Further Study 82
3 Matroid Intersection 84
3.1 Applications 84
3.2 An Efficient Cardinality Matroid-Intersection
Algorithm and Consequences 89
3.3 An Efficient Maximum-Weight Matroid-Intersection Algorithm 101
3.4 The Matroid-Intersection Polytope 103
3.5 Further Study 106
4 Matching 107
4.1 Augmenting Paths and Matroids 107
4.2 The Matching Polytope 109
4.3 Duality and a Maximum-Cardinality Matching Algorithm 113
4.4 Kuhn’s Algorithm for the Assignment Problem 121
4.5 Applications of Weighted Matching 126
4.6 Further Study 137
5 Flows and Cuts 138
5.1 Source–Sink Flows and Cuts 138
5.2 An Efficient Maximum-Flow Algorithm and Consequences 140
5.3 Undirected Cuts 147
5.4 Further Study 150
6 Cutting Planes 151
6.1 Generic Cutting-Plane Method 151
6.2 Chvátal–Gomory Cutting Planes 152
6.3 Gomory Cutting Planes 156
6.4 Tightening a Constraint 167
6.5 Constraint Generation for Combinatorial-Optimization
Problems 171
6.6 Further Study 176
7 Branch-&-Bound 177
7.1 Branch-&-Bound Using Linear-Programming Relaxation 179
7.2 Knapsack Programs and Group Relaxation 184
7.3 Branch-&-Bound for Optimal-Weight Hamiltonian Tour 188
Cambridge
Published online by Cambridge Books
University Press Online © Cambridge University Press, 2010
P1: IML/SPH P2: IML/SPH QC: IML/SPH T1: IML
CB636-FM CB636-Lee [Link] December 11, 2003 16:30 Char Count= 0
Contents xi
7.4 Maximum-Entropy Sampling and Branch-&-Bound 191
7.5 Further Study 193
8 Optimizing Submodular Functions 194
8.1 Minimizing Submodular Functions 194
8.2 Minimizing Submodular Functions Over Odd Sets 197
8.3 Maximizing Submodular Functions 200
8.4 Further Study 201
Appendix: Notation and Terminology 203
A.1 Sets 203
A.2 Algebra 203
A.3 Graphs 204
A.4 Digraphs 205
References 207
Background Reading 207
Further Reading 207
Indexes 209
Examples 209
Exercises 209
Problems 209
Results 210
Algorithms 211
Cambridge
Published online by Cambridge Books
University Press Online © Cambridge University Press, 2010
P1: IML/SPH P2: IML/SPH QC: IML/SPH T1: IML
CB636-FM CB636-Lee [Link] December 11, 2003 16:30 Char Count= 0
Cambridge
Published online by Cambridge Books
University Press Online © Cambridge University Press, 2010
xii