Title :
A Las Vegas algorithm for linear programming when the dimension is small
Author :
Clarkson, Kenneih L.
Author_Institution :
AT&T Bell Lab., Murray Hill, NJ, USA
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 :
computational complexity; linear programming; Las Vegas algorithm; arithmetic operations; bound; convex programming; linear programming; random choices; Arithmetic; Chebyshev approximation; Costs; Linear approximation; Linear matrix inequalities; Linear programming; Sampling methods;
Conference_Titel :
Foundations of Computer Science, 1988., 29th Annual Symposium on
Conference_Location :
White Plains, NY
Print_ISBN :
0-8186-0877-3
DOI :
10.1109/SFCS.1988.21961
