A Survey of Linear Programming in Randomized Subexponential Time

by Michael Goldwasser

Abstract:
``It is remarkable to see how different paths have led to rather similar results so close in time.'' -- Gil Kalai, (STOC 1992).
Three papers were published in 1992, each providing a combinatorial, randomized algorithm solving linear programming in subexponential expected time. Bounds on independent algorithms were proven, one by Kalai, and the other by Matousek, Sharir, and Welzl. Results by Gartner combined techniques from these papers to solve a much more general optimization problem in similar time bounds.

Although the algorithms by Kalai and Sharir-Welzl seem remarkably different in style and evolution, this paper demonstrates that one of the variants of Kalai's algorithm is identical (although dual) to the algorithm of Sharir-Welzl. Also the implication of Gartner's framework on future improvements is examined more carefully.


Citation:
A Survey of Linear Programming in Randomized Subexponential Time
Michael Goldwasser
SIGACT News 26:2, 1995, pp. 96-104.
DOI:10.1145/202840.202847
Download as: [ pdf, pdf.gz, ps, ps.Z, ps.gz ]

Michael Goldwasser