| Article ID: | iaor1999935 |
| Country: | Netherlands |
| Volume: | 79 |
| Issue: | 1/3 |
| Start Page Number: | 217 |
| End Page Number: | 233 |
| Publication Date: | Oct 1997 |
| Journal: | Mathematical Programming |
| Authors: | Kalai Gil |
In the first part of the paper we survey some far-reaching applications of the basic facts of linear programming to the combinatorial theory of simple polytopes. In the second part we discuss some recent developments concerning the simplex algorithm. We describe subexponential randomized pivot rules and upper bounds on the diameter of graphs of polytopes.