Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-156 | 13th December 2005 00:00

A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version)


Authors: Jonathan A. Kelner, Daniel A. Spielman
Publication: 19th December 2005 02:11
Downloads: 1543


We present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to represent its input.

We begin by reducing the input linear program to a special form in which we merely need to certify boundedness. As boundedness does not depend upon the right-hand-side vector, we run the shadow-vertex simplex method with a random right-hand-side vector. Thus, we do not need to bound the diameter of the original polytope.

Our analysis rests on a geometric statement of independent interest: given a polytope $A x \leq b$ in isotropic position, if one makes a polynomially small perturbation to $b$ then the number of edges of the projection of the perturbed polytope onto a random 2-dimensional subspace is expected to be polynomial.

ISSN 1433-8092 | Imprint