Paper Info
Title
A survey of linear programming in randomized subexponential time
Abstract
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 Gärtner 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 Gärtner's framework on future improvements is examined more carefully.
Year
DOI
Venue
1995
10.1145/202840.202847
SIGACT News
Keywords
Field
DocType
subexponential expected time,randomized algorithm,randomized subexponential time,linear programming,future improvement,independent algorithm,rtner combined technique,general optimization problem,similar time bound,linear program,optimization problem
Randomized algorithm,Combinatorics,Computer science,Theoretical computer science,Linear programming,Optimization problem,LP-type problem
Journal
Volume
Issue
Citations 
26
2
13
PageRank 
References 
Authors
1.04
11
1
Name
Order
Citations
PageRank
Michael Goldwasser1734.83