Table of contents for Understanding and using linear programming / Jiri Matousek, Bernd Ga╠łrtner.


Bibliographic record and links to related information available from the Library of Congress catalog
Note: Electronic data is machine generated. May be incomplete or contain other coding.


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



Library of Congress subject headings for this publication: Linear programming