DocumentCode
3174755
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
fYear
1988
fDate
24-26 Oct 1988
Firstpage
452
Lastpage
456
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1988., 29th Annual Symposium on
Conference_Location
White Plains, NY
Print_ISBN
0-8186-0877-3
Type
conf
DOI
10.1109/SFCS.1988.21961
Filename
21961
Link To Document