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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K.L. Clarkson, “Linear programming in\(O(n \times 3^{d^2 } )\) time,”Information Processing Letters 22 (1986) 21–24.
K.L. Clarkson, “New applications of random sampling to computational geometry,”Journal of Discrete and Computational Geometry 2 (1987), 195–222.
M.E. Dyer, “Linear time algorithms for two- and three-variable linear programs,”SIAM Journal on Computing 13 (1984) 31–45.
M.E. Dyer, “On a multidimensional search problem and its application to the Euclidean one-centre problem,”SIAM Journal on Computing 15 (1986) 725–738.
D. Haussler and E. Welzl, “ε-nets and simplex range queries,”Discrete and Computational Geometry 2 (1987) 127–151.
W. Hoeffding, “Probability inequalities for sums of bounded random variables,”Journal of the American Statistical Association 58 (1963) 13–30.
N. Megiddo, “Linear-time algorithms for linear programming ℝ3 and related problems,”SIAM Journal on Computing 12 (1983) 759–776.
N. Megiddo, “Linear programming in linear time when the dimension is fixed,”Journal of the Association for Computing Machinery 31 (1984) 114–127.
A. Schrijver,Theory of Linear and Integer Programming (Wiley, Chichester, 1986).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Dyer, M.E., Frieze, A.M. A randomized algorithm for fixed-dimensional linear programming. Mathematical Programming 44, 203–212 (1989). https://doi.org/10.1007/BF01587088
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01587088