Geometric Algorithms and Combinatorial Optimization
Başlık:
Geometric Algorithms and Combinatorial Optimization
ISBN:
9783642978814
Personal Author:
Edition:
1st ed. 1988.
Yayın Bilgileri:
Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1988.
Fiziksel Tanımlama:
XII, 362 p. online resource.
Series:
Algorithms and Combinatorics, 2
Contents:
0. Mathematical Preliminaries -- 0.1 Linear Algebra and Linear Programming -- 0.2 Graph Theory -- 1. Complexity, Oracles, and Numerical Computation -- 1.1 Complexity Theory: P and NP -- 1.2 Oracles -- 1.3 Approximation and Computation of Numbers -- 1.4 Pivoting and Related Procedures -- 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 -- 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 -- 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 -- 8.5 Matchings, Odd Cuts, and Generalizations -- 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 -- 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 -- 10.3 Submodular Functions on Lattice, Intersecting, and Crossing Families -- 10.4 Odd Submodular Function Minimization and Extensions -- References -- Notation Index -- Author Index.
Abstract:
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.
Subject Term:
Ek Kurum Yazarı:
Dil:
English