All reports by Author Daniel A. Spielman:

__
TR05-156
| 13th December 2005
__

Jonathan A. Kelner, Daniel A. Spielman#### A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version)

Jonathan A. Kelner, Daniel A. Spielman

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 ... more >>>