Geometric Algorithms and Combinatorial Optimization
Published on 24. March 1988
Book
Hardback
XII, 362 pages
978-3-540-13624-8 (ISBN)
Description
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.
More details
Series
Language
English
Place of publication
Heidelberg
Germany
Publishing group
Springer Berlin
Target group
College/higher education
Professional and scholarly
Illustrations
213 figures
Dimensions
Height: 24.2 cm
Width: 17 cm
Weight
810 gr
ISBN-13
978-3-540-13624-8 (9783540136248)
DOI
10.1007/978-3-642-97881-4
Schweitzer Classification
Other editions
New editions
Martin Grötschel | Laszlo Lovasz | Alexander Schrijver
Geometric Algorithms and Combinatorial Optimization
Book
09/1993
2nd Edition
Springer
€85.55
Article exhausted; check different version
Content
0. Mathematical Preliminaries.- 0.1 Linear Algebra and Linear Programming.- Basic Notation.- Hulls, Independence, Dimension.- Eigenvalues, Positive Definite Matrices.- Vector Norms, Balls.- Matrix Norms.- Some Inequalities.- Polyhedra, Inequality Systems.- Linear (Diophantine) Equations and Inequalities.- Linear Programming and Duality.- 0.2 Graph Theory.- Graphs.- Digraphs.- Walks, Paths, Circuits, Trees.- 1. Complexity, Oracles, and Numerical Computation.- 1.1 Complexity Theory: P and NP.- Problems.- Algorithms and Turing Machines.- Encoding.- Time and Space Complexity.- Decision Problems: The Classes, P and NP.- 1.2 Oracles.- The Running Time of Oracle Algorithms.- Transformation and Reduction.- NP-Completeness and Related Notions.- 1.3 Approximation and Computation of Numbers.- Encoding Length of Numbers.- Polynomial and Strongly Polynomial Computations.- Polynomial Time Approximation of Real Numbers.- 1.4 Pivoting and Related Procedures.- Gaussian Elimination.- Gram-Schmidt Orthogonalization.- The Simplex Method.- Computation of the Hermite Normal Form.- 2. Algorithmic Aspects of Convex Sets: Formulation of the Problems.- 2.1 Basic Algorithmic Problems for Convex Sets.- 2.2 Nondeterministic Decision Problems for Convex Sets.- 3. The Ellipsoid Method.- 3.1 Geometric Background and an Informal Description.- Properties of Ellipsoids.- Description of the Basic Ellipsoid Method.- Proofs of Some Lemmas.- Implementation Problems and Polynomiality.- Some Examples.- 3.2 The Central-Cut Ellipsoid Method.- 3.3 The Shallow-Cut Ellipsoid Method.- 4. Algorithms for Convex Bodies.- 4.1 Summary of Results.- 4.2 Optimization from Separation.- 4.3 Optimization from Membership.- 4.4 Equivalence of the Basic Problems.- 4.5 Some Negative Results.- 4.6 Further Algorithmic Problems for Convex Bodies.- 4.7 Operations on Convex Bodies.- The Sum.- The Convex Hull of the Union.- The Intersection.- Polars, Blockers, Antiblockers.- 5. Diophantine Approximation and Basis Reduction.- 5.1 Continued Fractions.- 5.2 Simultaneous Diophantine Approximation: Formulation of the Problems.- 5.3 Basis Reduction in Lattices.- 5.4 More on Lattice Algorithms.- 6. Rational Polyhedra.- 6.1 Optimization over Polyhedra: A Preview.- 6.2 Complexity of Rational Polyhedra.- 6.3 Weak and Strong Problems.- 6.4 Equivalence of Strong Optimization and Separation.- 6.5 Further Problems for Polyhedra.- 6.6 Strongly Polynomial Algorithms.- 6.7 Integer Programming in Bounded Dimension.- 7. Combinatorial Optimization: Some Basic Examples..- 7.1 Flows and Cuts.- 7.2 Arborescences.- 7.3 Matching.- 7.4 Edge Coloring.- 7.5 Matroids.- 7.6 Subset Sums.- 7.7 Concluding Remarks.- 8. Combinatorial Optimization: A Tour d'Horizon.- 8.1 Blocking Hypergraphs and Polyhedra.- 8.2 Problems on Bipartite Graphs.- 8.3 Flows, Paths, Chains, and Cuts.- 8.4 Trees, Branchings, and Rooted and Directed Cuts.- Arborescences and Rooted Cuts.- Trees and Cuts in Undirected Graphs.- Dicuts and Dijoins.- 8.5 Matchings, Odd Cuts, and Generalizations.- Matching.- b-Matching.- T-Joins and T-Cuts.- Chinese Postmen and Traveling Salesmen.- 8.6 Multicommodity Flows.- 9. Stable Sets in Graphs.- 9.1 Odd Circuit Constraints and t-Perfect Graphs.- 9.2 Clique Constraints and Perfect Graphs.- Antiblockers of Hypergraphs.- 9.3 Orthonormal Representations.- 9.4 Coloring Perfect Graphs.- 9.5 More Algorithmic Results on Stable Sets.- 10. Submodular Functions.- 10.1 Submodular Functions and Polymatroids.- 10.2 Algorithms for Polymatroids and Submodular Functions.- Packing Bases of a Matroid.- 10.3 Submodular Functions on Lattice, Intersecting, and Crossing Families.- 10.4 Odd Submodular Function Minimization and Extensions.- References.- Notation Index.- Author Index.