Geometric algorithms and combinatorial optimization

This book develops geometric techniques for proving the polynomial time solvability of problems in convexity theory, geometry, and - in particular - combinatorial optimization. It offers a unifying approach based on two fundamental geometric algorithms: - the ellipsoid method for finding a point in a convex set and - the basis reduction method for point lattices. The ellipsoid method was used by Khachiyan to show the polynomial time solvability of linear programming. The basis reduction method yields a polynomial time procedure for certain diophantine approximation problems. A combination of these techniques makes it possible to show the polynomial time solvability of many questions concerning poyhedra - for instance, of linear programming problems having possibly exponentially many inequalities. Utilizing results from polyhedral combinatorics, it provides short proofs of the poynomial time solvability of many combinatiorial optimization problems. For a number of these problems, the geometric algorithms discussed in this book are the only techniques known to derive polynomial time solvability. This book is a continuation and extension of previous research of the authors for which they received the Fulkerson Prize, awarded by the Mathematical Programming Society and the American Mathematical Society. VORBLATT......Page 1 TITELBLATT......Page 3 IMPRESSUM......Page 4 VORWORT......Page 5 VERZEICHNIS_INHALT......Page 9 Basic Notation......Page 13 Hulls, Independence, Dimension......Page 15 Eigenvalues, Positive Definite Matrices......Page 16 Vector Norms, Balls......Page 17 Matrix Norms......Page 19 Some Inequalities......Page 20 Polyhedra, Inequality Systems......Page 21 Linear (Diophantine) Equations and Inequalities......Page 23 Linear Programming and Duality......Page 26 0.2 Graph Theory......Page 28 Graphs......Page 29 Digraphs......Page 30 Walks, Paths, Circuits, Trees......Page 31 Problems......Page 33 Algorithms and Turing Machines......Page 34 Time and Space Complexity......Page 35 Decision Problems: The Classes P and NP......Page 36 The Running Time of Oracle Algorithms......Page 38 Transformation and Reduction......Page 39 NP-Completeness and Related Notions......Page 40 Encoding Length of Numbers......Page 41 Polynomial and Strongly Polynomial Computations......Page 44 Polynomial Time Approximation of Real Numbers......Page 45 Gaussian Elimination......Page 48 Gram-Schmidt Orthogonalization......Page 52 The Simplex Method......Page 53 Computation of the Hermite Normal Form......Page 55 Chapter 2: Algorithmic Aspects of Convex Sets: Formulation of the Problems......Page 58 2.1 Basic Algorithmic Problems for Convex Sets......Page 59 2.2 Nondeterministic Decision Problems for Convex Sets......Page 68 Chapter 3. The Ellipsoid Method......Page 76 Properties of Ellipsoids......Page 78 Description of the Basuc Ellipsoid Method......Page 85 Proofs of Some Lemmas......Page 88 Implementation Problems and Polynomiality......Page 92 Some Examples......Page 95 3.2 The Central-Cut Ellipsoid Method......Page 98 3.3 The Shallow-Cut Ellipsoid Method......Page 106 4.1 Summary of Results......Page 114 4.2 Optimization from Separation......Page 117 4.3 Optimization from Membership......Page 119 4.4 Equivalence of the Basic Problems......Page 126 4.5 Some Negative Results......Page 130 4.6 Further Algorithmic Problems for Convex Bodies......Page 134 The Sum......Page 140 The Intersection......Page 141 Polars. Blockers, Antiblockers......Page 143 Chapter 5. Diophantie Approximation and Basic Reduction......Page 145 5.1 Continued Fractions......Page 146 5.2 Simultaneous Diophantine Approximation: Formulation of the Problems......Page 150 5.3 Basic Reduction in Lattices......Page 151 5.4 More on Lattice Algorithms......Page 162 6.1 Optimization over Polyhedra: A Preview......Page 169 6.2 Complexity of Rational Polyhedra......Page 174 6.3 Weak and Strong Problems......Page 182 6.4 Equivalence of Strong Optimization and Separation......Page 186 6.5 Further Problems for Polyhedra......Page 193 6.6 Strongly Polynomial Algorithms......Page 200 6.7 Integer Programming in Bounded Dimension......Page 204 7.1 Flows and Cuts......Page 209 7.2 Arborescences......Page 213 7.3 Matching......Page 215 7.4 Edge Coloring......Page 220 7.5 Matroids......Page 222 7.6 Subset Sums......Page 230 7.7 Concluding Remarks......Page 233 8.1 Blocking Hypergraphs and Polyhedra......Page 237 8.2 Problems on Bipartite Graphs......Page 241 8.3 Flows, Paths, Chains, and Cuts......Page 245 Arborescences and Rooted Cuts......Page 254 Trees and Cuts in Undirected Graphs......Page 259 Dicuts and Dijoins......Page 263 8.5 Matchings, Odd Cuts, and Generalizations......Page 266 Matching......Page 267 b-Matching......Page 269 T-Joins and T-Cuts......Page 271 Cinese Postmen and Traveling Salesmen......Page 274 8.6 Milticommodity Flows......Page 278 9.1 Odd Cicuit Constraints and t-Perfect Graphs......Page 284 9.2 Clique Constraints and Perfect Graphs......Page 288 Antiblockers of Hypergraphs......Page 296 9.3 Orthonormal Representations......Page 297 9.4 Coloring Perfect Graphs......Page 308 9.5 More Algorithmic Results on Stable Sets......Page 311 10.1 Submodular Functions and Polymatroids......Page 316 10.2 Algorithms for Polymatroids and Submodular Functions......Page 320 Packing Bases of a Matroid......Page 323 10.3 Submodular Functions an Lattce, Intersecting, and Crossing Families......Page 325 10.4 Odd Submodular Function Minimization and Extensions......Page 337 VERZEICHNIS_LITERATUR......Page 343 VERZEICHNIS_ABKUERZUNGEN......Page 359 Author Index......Page 363 Subject Index......Page 367 WERBUNG......Page 375 Five Basic Problems......Page 379 Historically, there is a close connection between geometry and optImization. This is illustrated by methods like the gradient method and the simplex method, which are associated with clear geometric pictures. In combinatorial optimization, however, many of the strongest and most frequently used algorithms are based on the discrete structure of the problems: the greedy algorithm, shortest path and alternating path methods, branch-and-bound, etc. In the last several years geometric methods, in particular polyhedral combinatorics, have played a more and more profound role in combinatorial optimization as well. Our book discusses two recent geometric algorithms that have turned out to have particularly interesting consequences in combinatorial optimization, at least from a theoretical point of view. These algorithms are able to utilize the rich body of results in polyhedral combinatorics. The first of these algorithms is the ellipsoid method, developed for nonlinear programming by N. Z. Shor, D. B. Yudin, and A. S. NemirovskiI. It was a great surprise when L. G. Khachiyan showed that this method can be adapted to solve linear programs in polynomial time, thus solving an important open theoretical problem. While the ellipsoid method has not proved to be competitive with the simplex method in practice, it does have some features which make it particularly suited for the purposes of combinatorial optimization. The second algorithm we discuss finds its roots in the classical'geometry of numbers', developed by Minkowski. This method has had traditionally deep applications in number theory, in particular in diophantine approximation.