Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JONATHAN A. KELNER:
All reports by Author Jonathan A. Kelner:

TR05-156 | 13th December 2005
Jonathan A. Kelner, Daniel A. Spielman

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

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




ISSN 1433-8092 | Imprint