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