One line and n points
We analyze a randomized pivoting process involving one line and n points in the plane. The process models the behavior of the RANDOM-EDGE simplex algorithm on simple polytopes with it facets in dimension n - 2. We obtain a tight O(log(2) n) bound for the expected number of pivot steps. This is the first nontrivial bound for RANDOM-EDGE, which goes beyond bounds for specific polytopes. The process itself can be interpreted as a simple algorithm for certain 2-variable linear programming problems, and we prove a tight Theta(n) bound for its expected runtime. (C) 2003 Wiley Periodicals, Inc.
randomization simplex algorithm linear programming random-edge pivot rule