Matou?ek J., Gartner B. Understanding and Using Linear Programming

Springer-Verlag Berlin Heidelberg, 2007. 226 p.
What Is It, and What For?
A Linear Program.
What Can Be Found in This Book.
Linear Programming and Linear Algebra.
Significance and History of Linear Programming.
Examples.
Optimized Diet: Wholesome and Cheap?
Flow in a Network.
ce Cream All Year Round.
Fitting a Line.
Separation of Points.
Largest Disk in a Convex Polygon.
Cutting Paper Rolls.
nteger Programming and LP Relaxation.
nteger Programming.
Maximum-Weight Matching.
Minimum Vertex Cover.
Maximum Independent Set.
Theory of Linear Programming:
First Steps.
Equational Form.
Basic Feasible Solutions.
ABC of Convexity and Convex Polyhedra.
ertices and Basic Feasible Solutions.
The Simplex Method.
An Introductory Example.
Exception Handling: Unboundedness.
Exception Handling: Degeneracy.
Exception Handling: Infeasibility.
Simplex Tableaus in General.
The Simplex Method in General.
The Struggle Against Cycling.
Efficiency of the Simplex Method.
Summary.
Duality of Linear Programming.
The Duality Theorem.
Dualization for Everyone.
Proof of Duality from the Simplex Method.
Proof of Duality from the Farkas Lemma.
Farkas Lemma: An Analytic Proof.
Farkas Lemma from Minimally Infeasible Systems.
Farkas Lemma from the Fourier–Motzkin Elimination.
Not Only the Simplex Method.
The Ellipsoid Method.
nterior Point Methods.
More Applications.
Zero-Sum Games.
Matchings and Vertex Covers in Bipartite Graphs.
Machine Scheduling.
Upper Bounds for Codes.
Sparse Solutions of Linear Systems.
Transversals of d-Intervals.
Smallest Balls and Convex Programming.
Software and Further Reading.
Appendix: Linear Algebra.
Glossary.
Index.