ISSN:
1436-4646
Keywords:
Linear programming
;
randomized algorithm
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We give a (Las Vegas) randomized algorithm for linear programming in a fixed dimensiond for which the expected computation time is $$O(d^{(3 + \varepsilon _d )d} n)$$ , where lim d→∞ ε d = 0. This improves the corresponding worst-case complexity, $$O(3^{d^2 } n)$$ . The method is based on a recent idea of Clarkson. Two variations on the algorithm are examined briefly.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01587088
Permalink