Understanding And Using Linear Programming

by Matousek, Jiri; Gartner, Bernd

• ISBN13: 9783540306979
• ISBN10: 3540306978
• Format: Paperback
• Copyright: 2007-01-30
• Publisher: Springer Nature

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".

Author Biography

Jiri Matousek is Professor of Computer Science at Charles University in Prague Bernd Gartner is senior researcher at the Institute of Theoretical Computer Science of ETH Zurich

Table of Contents

Preface	v
1. What Is It, and What For?	1	(10)
1.1 A Linear Program	1	(5)
1.2 What Can Be Found in This Book	6	(1)
1.3 Linear Programming and Linear Algebra	7	(1)
1.4 Significance and History of Linear Programming	8	(3)
2. Examples	11	(18)
2.1 Optimized Diet: Wholesome and Cheap?	12	(2)
2.2 Flow in a Network	14	(2)
2.3 Ice Cream All Year Round	16	(3)
2.4 Fitting a Line	19	(2)
2.5 Separation of Points	21	(2)
2.6 Largest Disk in a Convex Polygon	23	(3)
2.7 Cutting Paper Rolls	26	(3)
3. Integer Programming and LP Relaxation	29	(12)
3.1 Integer Programming	29	(2)
3.2 Maximum-Weight Matching	31	(6)
3.3 Minimum Vertex Cover	37	(2)
3.4 Maximum Independent Set	39	(2)
4. Theory of Linear Programming: First Steps	41	(16)
4.1 Equational Form	41	(3)
4.2 Basic Feasible Solutions	44	(4)
4.3 ABC of Convexity and Convex Polyhedra	48	(5)
4.4 Vertices and Basic Feasible Solutions	53	(4)
5. The Simplex Method	57	(24)
5.1 An Introductory Example	57	(4)
5.2 Exception Handling: Unboundedness	61	(1)
5.3 Exception Handling: Degeneracy	62	(1)
5.4 Exception Handling: Infeasibility	63	(2)
5.5 Simplex Tableaus in General	65	(1)
5.6 The Simplex Method in General	66	(5)
5.7 Pivot Rules	71	(1)
5.8 The Struggle Against Cycling	72	(4)
5.9 Efficiency of the Simplex Method	76	(3)
5.10 Summary	79	(2)
6. Duality of Linear Programming	81	(24)
6.1 The Duality Theorem	81	(3)
6.2 Dualization for Everyone	84	(3)
6.3 Proof of Duality from the Simplex Method	87	(2)
6.4 Proof of Duality from the Farkas Lemma	89	(6)
6.5 Farkas Lemma: An Analytic Proof	95	(2)
6.6 Farkas Lemma from Minimally Infeasible Systems	97	(3)
6.7 Farkas Lemma from the Fourier–Motzkin Elimination	100	(5)
7. Not Only the Simplex Method	105	(26)
7.1 The Ellipsoid Method	106	(9)
7.2 Interior Point Methods	115	(16)
8. More Applications	131	(62)
8.1 Zero-Sum Games	131	(11)
8.2 Matchings and Vertex Covers in Bipartite Graphs	142	(6)
8.3 Machine Scheduling	148	(8)
8.4 Upper Bounds for Codes	156	(11)
8.5 Sparse Solutions of Linear Systems	167	(10)
8.6 Transversals of d-Intervals	177	(7)
8.7 Smallest Balls and Convex Programming	184	(9)
9. Software and Further Reading	193	(2)
Appendix: Linear Algebra	195	(6)
Glossary	201	(16)
Index	217