Geometric Algorithms and Combinatorial Optimization
Springer Berlin (Verlag)
978-3-642-78242-8 (ISBN)
Prof. Dr. Dr. h.c. mult. Martin Grötschel, Technische Universität Berlin, Zuse-Institut Berlin (ZIB) und MATHEON.
László Lovász ist einer der Leiter der theoretischen Forschungsabteilung der Microsoft Corporation. Er hat 1999 den Wolf-Preis sowie den Gödel-Preis für die beste wissenschaftliche Veröffentlichung in der Informatik erhalten.
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.
Erscheint lt. Verlag | 21.12.2011 |
---|---|
Reihe/Serie | Algorithms and Combinatorics |
Zusatzinfo | XII, 362 p. |
Verlagsort | Berlin |
Sprache | englisch |
Maße | 170 x 242 mm |
Gewicht | 648 g |
Themenwelt | Mathematik / Informatik ► Mathematik ► Graphentheorie |
Schlagworte | Algorithmen • algorithms • Basis Reduction in Lattices • Basisreduktion bei Gittern • combinatorial optimization • combinatorics • Convexity • Ellipsoid Method • Ellipsoidmethode • Kombinatorische Optimierung • Konvexität • lattice • Lineares Programmieren • Linear Programming • operations resear |
ISBN-10 | 3-642-78242-6 / 3642782426 |
ISBN-13 | 978-3-642-78242-8 / 9783642782428 |
Zustand | Neuware |
Haben Sie eine Frage zum Produkt? |
aus dem Bereich