A Las Vegas algorithm for linear programming when the dimension is small
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 452-456
- https://doi.org/10.1109/sfcs.1988.21961
Abstract
An algorithm for solving linear programming problems is given. The expected number of arithmetic operations required by the algorithm is given. The expectation is with respect to the random choices made by the algorithm, and the bound holds for any given input. The technique can be extended to other convex programming problems.Keywords
This publication has 6 references indexed in Scilit:
- Applications of random sampling in computational geometry, IIPublished by Association for Computing Machinery (ACM) ,1988
- New applications of random sampling in computational geometryDiscrete & Computational Geometry, 1987
- 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
- Linear Programming in Linear Time When the Dimension Is FixedJournal of the ACM, 1984
- Optimality and Degeneracy in Linear ProgrammingEconometrica, 1952