Contents v
9. An Application: The Transportation Problem 176
10. Semidefinite Programming 178
11. An Application: The Clique and Chromatic Numbers of a
Graph 182
12. Linear Programming in
L∞
185
13. Uniform Approximation as a Linear Programming Problem 191
14. The Mass-Transfer Problem 196
15. Remarks 202
Chapter V. Convex Bodies and Ellipsoids 203
1. Ellipsoids 203
2. The Maximum Volume Ellipsoid of a Convex Body 207
3. Norms and Their Approximations 216
4. The Ellipsoid Method 225
5. The Gaussian Measure on Euclidean Space 232
6. Applications to Low Rank Approximations of Matrices 240
7. The Measure and Metric on the Unit Sphere 244
8. Remarks 248
Chapter VI. Faces of Polytopes 249
1. Polytopes and Polarity 249
2. The Facial Structure of the Permutation Polytope 254
3. The Euler-Poincar´ e Formula 258
4. Polytopes with Many Faces: Cyclic Polytopes 262
5. Simple Polytopes 264
6. The h-vector of a Simple Polytope.
Dehn-Sommerville Equations 267
7. The Upper Bound Theorem 270
8. Centrally Symmetric Polytopes 274
9. Remarks 277
Chapter VII. Lattices and Convex Bodies 279
1. Lattices 279
2. The Determinant of a Lattice 286
3. Minkowski’s Convex Body Theorem 293
Previous Page Next Page