Iterative methods in combinatorial optimization

Cover......Page 1
Half-title......Page 3
Series-title......Page 4
Title......Page 5
Copyright......Page 6
Contents......Page 7
Audience......Page 11
Acknowledgments......Page 12
Dedications......Page 13
1.1 The assignment problem......Page 15
1.2 Iterative algorithm......Page 17
1.2.1 Contradiction proof idea: Lower bound > upper bound......Page 18
1.3 Approach outline......Page 19
1.5 Book chapters overview......Page 22
1.6 Notes......Page 24
2.1 Linear programming......Page 26
2.1.1 Extreme point solutions to linear programs......Page 27
2.1.1.1 Basic feasible solution......Page 29
2.1.2 Algorithms for linear programming......Page 30
2.1.4 Linear programming duality......Page 31
2.1.4.1 Complementary slackness conditions......Page 32
2.2 Graphs and digraphs......Page 33
2.3.1 Submodularity......Page 35
2.3.3 Refinements......Page 37
2.3.3.1 Minimizing submodular function......Page 39
Exercises......Page 40
3.1 Matchings in bipartite graphs......Page 42
3.1.2 Characterization of extreme point solutions......Page 43
3.1.4 Correctness and optimality......Page 44
3.2.1 Linear programming relaxation......Page 46
3.2.4 Correctness and performance guarantee......Page 47
3.3 Maximum budgeted allocation......Page 49
3.3.1 Linear programming relaxation......Page 50
3.3.3 An iterative 2-approximation algorithm......Page 51
3.3.4 An iterative -approximation algorithm......Page 52
3.3.5 Correctness and performance guarantee......Page 53
3.4 Vertex cover in bipartite graphs......Page 54
3.4.2 Characterization of extreme point solutions......Page 55
3.4.4 Correctness and optimality......Page 56
3.5 Vertex cover and matching: duality......Page 57
Exercises......Page 58
4.1 Minimum spanning trees......Page 60
4.1.1 Linear Programming Relaxation......Page 61
4.1.3 Uncrossing technique......Page 64
4.1.5 Correctness and optimality of leaf-finding algorithm......Page 67
4.2 Iterative 1-edge-finding algorithm......Page 68
4.2.1 Correctness and optimality of 1-edge-finding algorithm......Page 69
4.3.1 Linear programming relaxation......Page 71
4.3.3 Leaf-finding iterative algorithm......Page 72
4.3.4 Correctness and performance guarantee......Page 73
4.4.1 Correctness and performance guarantee......Page 74
Exercises......Page 76
5.1 Preliminaries......Page 79
5.2.1 Linear programming formulation......Page 81
5.2.2 Characterization of extreme point solutions......Page 82
5.2.4 Correctness and optimality......Page 83
5.3 Matroid intersection......Page 85
5.3.2 Characterization of extreme point solutions......Page 86
5.3.4 Correctness and optimality......Page 87
5.4.1 Dual of maximum weight basis......Page 88
5.4.2 Dual of two matroid intersection......Page 90
5.5 Minimum bounded degree matroid basis......Page 91
5.5.1 Linear programming relaxation......Page 92
5.5.4 Correctness and performance guarantee......Page 93
5.5.5 Applications......Page 94
5.6.1 Linear programming relaxation......Page 96
5.6.4 Correctness and performance guarantee......Page 97
5.7 Notes......Page 99
Exercises......Page 100
6 Arborescence and rooted connectivity......Page 102
6.1.1 Linear programming relaxation......Page 103
6.1.2 Characterization of extreme point solutions......Page 104
6.1.4 Correctness and optimality......Page 106
6.2.1 Linear programming relaxation......Page 109
6.2.2 Iterative algorithm......Page 111
6.2.3 Characterization of extreme point solutions......Page 112
6.2.4 Correctness and optimality......Page 113
6.3 Minimum bounded degree arborescence......Page 115
6.3.1 Linear programming relaxation......Page 116
6.3.4 Correctness and performance guarantee......Page 117
6.4.1 Iterative algorithm......Page 120
6.4.2 Correctness and performance guarantee......Page 121
6.5 Notes......Page 122
Exercises......Page 123
7.1 The model and the main result......Page 124
7.1.2 Generalizing to submodular functions......Page 125
7.2 Primal integrality......Page 126
7.2.2 Characterization of extreme point solutions......Page 127
7.2.4 Correctness and optimality......Page 128
7.3 Dual integrality......Page 130
7.4.1 Directed cut cover and feedback arc set......Page 131
7.4.2 Polymatroid intersection......Page 133
7.4.3 Graph orientation......Page 136
7.5.1 Linear Programming Relaxation......Page 138
7.5.3 Iterative algorithm......Page 139
7.5.5 Applications......Page 141
7.6 Notes......Page 142
Exercises......Page 143
8.1 The model and main results......Page 145
8.2.3 Iterative algorithm......Page 147
8.2.4 Correctness and optimality......Page 148
8.3.1 Linear programming relaxation......Page 150
8.3.4 Correctness and optimality......Page 151
8.4.1 Matroid......Page 153
8.4.2 Matroid intersection......Page 154
8.4.3 Submodular flows......Page 156
Exercises......Page 157
9.1.1 Linear programming relaxation......Page 159
9.1.2 Characterization of extreme point solutions......Page 160
9.1.4 Correctness and optimality......Page 164
9.2.1 Linear programming relaxation......Page 169
9.2.3 Iterative algorithm and local ratio method......Page 170
9.3 Notes......Page 174
Exercises......Page 175
10.1 Survivable network design problem......Page 178
10.1.2 Characterization of extreme point solutions......Page 179
10.1.4 Correctness and performance guarantee......Page 180
10.2.1 Linear programming relaxation......Page 182
10.2.3 Existence of edges with large fractional value......Page 183
10.3 Minimum bounded degree Steiner networks......Page 186
10.3.2 Characterization of extreme point solutions......Page 187
10.3.4 Correctness and performance guarantee......Page 188
10.4.2 Correctness and performance guarantee......Page 189
10.5 Notes......Page 193
Exercises......Page 194
11.1.1 Linear programming relaxation......Page 196
11.1.4 Correctness and performance guarantee......Page 197
11.2 Partial vertex cover......Page 198
11.2.2 Characterization of extreme point solutions......Page 199
11.2.4 Correctness and performance guarantee......Page 200
11.3.1 Linear programming relaxation......Page 201
11.3.4 Correctness and performance guarantee......Page 202
Exercises......Page 203
12.1.1 Linear programming relaxation......Page 205
12.1.3 Correctness and performance guarantee......Page 206
12.2 Feedback vertex set on bipartite tournaments......Page 208
12.2.3 Correctness and performance guarantee......Page 209
12.3.1 Linear programming relaxation......Page 211
12.3.3 Correctness and performance guarantee......Page 212
Exercises......Page 214
13.1 A discrepancy theorem......Page 217
13.1.4 Correctness and performance guarantee......Page 218
13.2.2 Characterization of extreme point solutions......Page 220
13.2.4 Correctness and performance guarantee......Page 221
13.3.1 Linear programming relaxation......Page 222
13.3.4 Correctness and optimalit......Page 223
13.4 Minimum cost unsplittable flow......Page 224
13.4.3 Correctness and performance guarantee......Page 225
13.5 Bin packing......Page 226
13.5.1 Linear programming relaxation......Page 227
13.5.2 Characterization of extreme point solutions......Page 229
13.5.3.1 Linear grouping......Page 230
13.5.3.3 Elimination of small items......Page 231
13.5.5 Correctness and performance guarantee......Page 232
13.6 Iterative randomized rofinding: Steiner trees......Page 234
13.6.1 Linear programming relaxation......Page 235
13.6.2 Iterative randomized rofinding......Page 236
13.6.3.1 Preparations......Page 238
13.6.3.2 Inductive analysis......Page 241
13.7 Notes......Page 242
Exercises......Page 243
14 Summary......Page 245
Bibliography......Page 247
Index......Page 255