A survey of linear programming in randomized subexponential time
- 1 June 1995
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 26 (2) , 96-104
- https://doi.org/10.1145/202840.202847
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.Keywords
This publication has 11 references indexed in Scilit:
- Randomized simplex algorithms on Klee-Minty cubesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A subexponential randomized simplex algorithm (extended abstract)Published by Association for Computing Machinery (ACM) ,1992
- A subexponential algorithm for abstract optimization problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Small-dimensional linear programming and convex hulls made easyDiscrete & Computational Geometry, 1991
- A Las Vegas algorithm for linear programming when the dimension is smallPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre ProblemSIAM Journal on Computing, 1986
- Linear programming in O(n × 3d) timeInformation Processing Letters, 1986
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984
- Linear Programming in Linear Time When the Dimension Is FixedJournal of the ACM, 1984
- Polynomial algorithms in linear programmingUSSR Computational Mathematics and Mathematical Physics, 1980