| Preface | p. ix |
| Introduction | p. 1 |
| The assignment problem | p. 1 |
| Iterative algorithm | p. 3 |
| Approach outline | p. 5 |
| Context and applications of iterative rounding | p. 8 |
| Book chapters overview | p. 8 |
| Notes | p. 10 |
| Preliminaries | p. 12 |
| Linear programming | p. 12 |
| Graphs and digraphs | p. 19 |
| Submodular and supermodular functions | p. 21 |
| Matching and vertex cover in bipartite graphs | p. 28 |
| Matchings in bipartite graphs | p. 28 |
| Generalized assignment problem | p. 32 |
| Maximum budgeted allocation | p. 35 |
| Vertex cover in bipartite graphs | p. 40 |
| Vertex cover and matching: duality | p. 43 |
| Notes | p. 44 |
| Spanning trees | p. 46 |
| Minimum spanning trees | p. 46 |
| Iterative 1-edge-finding algorithm | p. 54 |
| Minimum bounded-degree spanning trees | p. 57 |
| An additive one approximation algorithm | p. 60 |
| Notes | p. 62 |
| Matroids | p. 65 |
| Preliminaries | p. 65 |
| Maximum weight basis | p. 67 |
| Matroid intersection | p. 71 |
| Duality and min-max theorem | p. 74 |
| Minimum bounded degree matroid basis | p. 77 |
| k matroid intersection | p. 82 |
| Notes | p. 85 |
| Arborescence and rooted connectivity | p. 88 |
| Minimum cost arborescence | p. 89 |
| Minimum cost rooted k-connected subgraphs | p. 95 |
| Minimum bounded degree arborescence | p. 101 |
| Additive performance guarantee | p. 106 |
| Notes | p. 108 |
| Submodular flows and applications | p. 110 |
| The model and the main result | p. 110 |
| Primal integrality | p. 112 |
| Dual integrality | p. 116 |
| Applications of submodular flows | p. 117 |
| Minimum bounded degree submodular flows | p. 124 |
| Notes | p. 128 |
| Network matrices | p. 131 |
| The model and main results | p. 131 |
| Primal integrality | p. 133 |
| Dual integrality | p. 136 |
| Applications | p. 139 |
| Notes | p. 143 |
| Matchings | p. 145 |
| Graph matching | p. 145 |
| Hypergraph matching | p. 155 |
| Notes | p. 160 |
| Network design | p. 164 |
| Survivable network design problem | p. 164 |
| Connection to the traveling salesman problem | p. 168 |
| Minimum bounded degree Steiner networks | p. 172 |
| An additive approximation algorithm | p. 175 |
| Notes | p. 179 |
| Constrained optimization problems | p. 182 |
| Vertex cover | p. 182 |
| Partial vertex cover | p. 184 |
| Multicriteria spanning trees | p. 187 |
| Notes | p. 189 |
| Cut problems | p. 191 |
| Triangle cover | p. 191 |
| Feedback vertex set on bipartite tournaments | p. 194 |
| Node multiway cut | p. 197 |
| Notes | p. 200 |
| Iterative relaxation: Early and recent examples | p. 203 |
| A discrepancy theorem | p. 203 |
| Rearrangments of sums | p. 206 |
| Minimum cost circulation | p. 208 |
| Minimum cost unsplittable flow | p. 210 |
| Bin packing | p. 212 |
| Iterative randomized rounding: Steiner trees | p. 220 |
| Notes | p. 228 |
| Summary | p. 231 |
| Bibliography | p. 233 |
| Index | p. 241 |
| Table of Contents provided by Ingram. All Rights Reserved. |