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