Geometric Algorithms and Combinatorial Optimization / by Martin Grötschel, László Lovász, Alexander Schrijver
(Algorithms and Combinatorics ; 2)
| データ種別 | 電子ブック |
|---|---|
| 出版情報 | Berlin, Heidelberg : Springer Berlin Heidelberg , 1988 |
| 本文言語 | 英語 |
| 大きさ | XII, 362p. 23 illus : online resource |
書誌詳細を非表示
| 内容注記 | 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 |
|---|---|
| 一般注記 | 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 |
| 著者標目 | *Grötschel, Martin author Lovász, László author Schrijver, Alexander author SpringerLink (Online service) |
| 件 名 | LCSH:Mathematics LCSH:Combinatorics FREE:Mathematics FREE:Combinatorics |
| 分 類 | DC23:511.6 |
| 巻冊次 | ISBN:9783642978814 
|
| ISBN | 9783642978814 |
| URL | http://dx.doi.org/10.1007/978-3-642-97881-4 |
目次／あらすじ