|
|
|||
|
||||
OverviewFull Product DetailsAuthor: Martin Grötschel , Laszlo Lovasz , Alexander SchrijverPublisher: Springer-Verlag Berlin and Heidelberg GmbH & Co. KG Imprint: Springer-Verlag Berlin and Heidelberg GmbH & Co. K Edition: 2nd ed. 1993. Softcover reprint of the original 2nd ed. 1993 Volume: 2 Dimensions: Width: 17.00cm , Height: 2.00cm , Length: 24.20cm Weight: 0.649kg ISBN: 9783642782428ISBN 10: 3642782426 Pages: 362 Publication Date: 21 December 2011 Audience: Professional and scholarly , Professional & Vocational Format: Paperback Publisher's Status: Active Availability: Manufactured on demand We will order this item for you from a manufactured on demand supplier. Table of Contents0. 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.ReviewsAuthor InformationTab Content 6Author Website:Countries AvailableAll regions |