Geometric Algorithms and Combinatorial Optimization

Chapters 7 to 10 contain the applications of the results obtained in the previous chapters to combinatorial optimization. Chapter 7 is an easy-to-read introduction to these applications. In Chapter 8 we give an in-depth survey of combinatorial optimization problems solvable in polynomial time with the methods of Chapter 6. Chapters 9 and 10 treat two specific areas where the ellipsoid method has resolved important algorithmic questions that so far have resisted direct combinatorial approaches: perfect graphs and submodular functions.We are grateful to several colleagues for many discussions on the topic and text of this book, in particular to 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. 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. By Martin Grötschel, László Lovász, Alexander Schrijver. 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 which is 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. 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. The first edition of this book was received enthusiastically by the community of discrete mathematicians, combinatorial optimizers, operations researchers, and computer scientists. To quote just from a few reviews: "The book is written in a very grasping way, legible both for people who are interested in the most important results and for people who are interested in technical details and proofs." #manuscripta geodaetica#1 Front Matter....Pages I-XII Mathematical Preliminaries....Pages 1-20 Complexity, Oracles, and Numerical Computation....Pages 21-45 Algorithmic Aspects of Convex Sets: Formulation of the Problems....Pages 46-63 The Ellipsoid Method....Pages 64-101 Algorithms for Convex Bodies....Pages 102-132 Diophantine Approximation and Basis Reduction....Pages 133-156 Rational Polyhedra....Pages 157-196 Combinatorial Optimization: Some Basic Examples....Pages 197-224 Combinatorial Optimization: A Tour d’Horizon....Pages 225-271 Stable Sets in Graphs....Pages 272-303 Submodular Functions....Pages 304-329 Back Matter....Pages 331-364