Research Catalog

Title

Understanding and using linear programming / Jiri Matousek, Bernd Gärtner.

Author

Matoušek, Jiří, 1963-

Publication

Berlin ; New York : Springer, c2007.

Items in the Library & Off-site

Details

Additional Authors

Gärtner, Bernd

Description

viii, 222 p. : ill.; 24 cm.

Summary

The book is an introductory textbook mainly for students of computer science and mathematics. Our guiding phrase is "what every theoretical computer scientist should know about linear programming". A major focus is on applications of linear programming, both in practice and in theory. The book is concise, but at the same time, the main results are covered with complete proofs and in sufficient detail, ready for presentation in class. The book does not require more prerequisites than basic linear algebra, which is summarized in an appendix. One of its main goals is to help the reader to see linear programming "behind the scenes".

Series Statement

Universitext

Uniform Title

Universitext

Subjects

• Textbooks
• Programming, Linear
• Operations Research/Decision Theory
• Mathematics of Computing
• Operations Research, Mathematical Programming
• Optimization
• Operations research
• Mathematical optimization
• Computer science
• Mathematics
• Linear programming

Genre/Form

Textbooks

Note

• Includes index.

Processing Action (note)

• committed to retain

Contents

• Preface -- 1. What is it, and what for? -- 1.2. A linear program -- 1.2. What can be found in this book -- 1.3. Linear programming and linear algebra -- 1.4. Significance and history of linear programming -- 2. Examples -- 2.1. Optimized diet : wholesome and cheap? -- 2.2. flow in a network -- 2.3. Ice cream all year round -- 2.4. Fitting a line -- 2.5. Separation of points -- 2.6. Largest disk in a convex polygon -- 2.7. Cutting paper rolls -- 3. Integer programming and LP relaxation -- 3.1. Integer programming -- 3.2. Maximum-weight matching -- 3.3. Minimum vertex cover -- 3.4. Maximum independent set -- 4. Theory of linear programming : first steps -- 4.1. Equational form -- 4.2. Basic feasible solutions -- 4.3. ABC of convexity and convex polyhedra -- 4.4. Vertices and basic feasible solutions.
• 5. The simple method -- 5.1. An introductory example -- 5.2. Exception handling : unboundedness -- 5.3. Exception handling : degeneracy -- 5.4. Exception handling : infeasibility -- 5.5. Simplex tableaus in general -- 5.6. The simplex method in general -- 5.7. Pivot rules -- 5.8. The struggle against cycling -- 5.9. Efficiency of the simplex method -- 5.10. Summary -- 6. Duality of linear programming -- 6.1. The duality theorem -- 6.2. Dualization for everyone -- 6.3. Proof of duality from the simplex method -- 6.4. Proof of duality from the Farkas lemma -- 6.5. Farkas lemma : an analytic proof -- 6.6. Farkas lemma from minimally infeasible systems -- 6.7. Farkas lemma from the Fourier-Motzkin elimination -- 7. Not only the simplex method -- 7.1. The ellipsoid method -- 7.2. Interior point methods -- 8. More applications -- 8.1. Zero-sum games -- 8.2. matchings and vertex covers in bipartite graphs -- 8.3. Machine scheduling -- 8.4. Upper bounds for codes -- 8.5. Sparse solutions of linear systems -- 8.6. Transversals of d-intervals -- 8.7. Smallest balls and convex programming -- 9. Software and further reading -- Appendix : Linear algebra -- Glossary -- Index.

ISBN

• 9783540306979 (acid-free paper)
• 3540307176 (acid-free paper)

LCCN

^^2006931795

OCLC

• 73108301
• SCSB-10105784

Owning Institutions

Harvard Library