Kenneth L. Clarkson
Abstract
This paper gives an algorithm for solving linear programming problems. For a problem with n constraints and d variables, the algorithm requires an expected O(d2n) + (log n)O(d)d/2+O(1) + O(d4√nlog n) arithmetic operations, as n→∞. The constant factors do not depend on d. Also, an algorithm is given for integer linear programming. Let φ bound the number of bits required to specify the rational numbers defining an input constraint or the objective function vector. Let n and d be as before. Then, the algorithm requires expected O(2d dn + 8dd√n ln ln n) + dO(d)φ ln n operations on numbers with dO(1)φ bits, as n→∞, where the constant factors do not depend on d or φ to other convex programming problems. For example, an algorithm for finding the smallest sphere enclosing a set of n points in Ed has the same time bound.
- ~ADLER, I. ~,ND SIIAMIR, R. 1990. A randomization scheme for speeding up algorithms for linear ~and convex quadratic programming problems with a high constraints-to-variables ratio. Tech. ~Rep. 21-90, Rutgers Univ., Rutgers, N.J., May. (Math. Prog. to appear.)Google Scholar
- ~ALON, N. AND MEGIDDO, N. 1990. Parallel linear programming m fixed dimension almost surely ~in constant time. In Proceedings of the 3}st IEEE Symposium on Fouttdations of Compztter ~Sctence. IEEE, New York, pp. 574 582.Google Scholar
- ~BABAI, L. 1985. On Lovfisz's lattice reduction and the nearest lattice point problem. In Lecture ~Notes in Computer Science, K. Mehlhorn, ed. Springer-Verlag, New York, pp. 13-20. Google Scholar
- ~BELL, D. E. 1977. A theorem concerning the integer lattice. Stud. Appl. Math. 56, 187-188.Google Scholar
- ~CHARNES, A. 1952. Optimality and degeneracy in linear programming. Econometrika 20, 160-170.Google Scholar
- ~CHAZELLE, B., AND MATOUSEK 1993. On linear-time deterministic algorithms for optimization ~problems in fixed dimension. In Proceedings of tile 4th ACM-SIAM Symposium on Discrete ~Algorithms. ACM, New York, 281-290. Google Scholar
- CLARKSON, K. L. 1986. Linear programming in O(n3a2) time. bzf. Proc. Lett. 22, 21-24. Google Scholar
- CLARKSON, K. L. 1987. New applications of random sampling in computational geometry. Disc. ~Comput. Geometry 2, 195-222.Google Scholar
- ~CLARKSON, m. L., AND SHOR, P. W. 1989. Applications of random sampling in computational ~geometry, II. Disc. Comput. Geometry 4, 387-421. Google Scholar
- ~DYER, M. E. 1986. On a multidimensional search technique and its application to the euclidean ~one-centre problem. SIAM J. Comput. 15, 725-738. Google Scholar
- ~DYER, M. E., AND FRIEZE. A. M. 1989. A randomized algorithm for fixed-dimensional linear ~programming. Math. Prog. 44, 203-212. Google Scholar
- ~FLIT, S. D. 1984. A fast algorithm for the two-variable integer programming problem. J. ACM, ~99-113. Google Scholar
- ~FRANK, A., AND TARDOS, 12. 1987. An application of simultaneous approximation in combinato- ~rial optimization. Combinatorica 7, 49-66. Google Scholar
- ~GILL, P. E., MURRAY, W., AND WRIGHT, M. H. 1981. Practical Optimtzatton. Academic Press, ~Orlando, Fla.Google Scholar
- ~GILL, P. E., MURRAY, W., AND WRIGHT, M. H. 1991. Numerical Linear Algebra and Optimization. ~Addison-Wesley, New York.Google Scholar
- ~HAUSSLER, D., AND WELZL, E. 1987. Epsilon-nets and simplex range queries. Dtsc. Comput. ~Geometry 2, 127-151.Google Scholar
- ~KALAI, G. 1992. A subexponential randomized simplex algorithm. In Proceedings of the 24th ~Annual. ACM Symposium on the Theory of Computing. Google Scholar
- ~KANNAN, R. 1987. Minkowski's convex body theorem and integer programming. Math. Oper. ~Res. 12, 415-440. Google Scholar
- ~KHACHIAN, L. G. 1980. Polynomial algorithms in linear programming, Z. Vych. Math. Mat. Fiz., ~53-72.Google Scholar
- ~KLEE, g., AND MINTY, G. J. 1972. HOW good is the simplex algorithm? In Inequalities III. ~Academic Press, Orlando, Fla.Google Scholar
- ~LENSTRA, H. W. 1983. Integer programming with a fixed number of variables. Math. Oper. Res., ~538-548.Google Scholar
- ~LITTLESTONE, N. Learning quickly when irrelevant attributes abound: A new linear-threshold ~algorithm. In Proceedings of the 28th IEEE Sympostum on Foundattons of Computer Science. ~IEEE, New York, pp. 68-77. Google Scholar
- ~MEGIDDO, N. 1984. Linear programming in linear time when the dimension is fixed. J. ACM31, ~114-127. Google Scholar
- ~MATOU~EK, J., SHARIR, M., AND WELZL, E. 1992. A subcxponential bound for linear program- ~ming. In Proceedings of the 8th Annual ACM Symposium Computational Geometry, ACM, New ~York, pp. 1-8. Google Scholar
- ~SCARF, H. E. 1977. An observation on the structure of production sets with indivisibilities. In ~Proceedings of the National Academy of Sciences of the United States of America 74, 3637-3641.Google Scholar
- ~SCHRIJVER, A. 1986. Theory of Linear and Integer Programmb~g. Wiley, New York. Google Scholar
- ~SEIDEL, R. 199l. Small-dimensional linear programming and convex hulls made easy. Disc. ~Comput. Geom. 6, 5, 423-433. Google Scholar
- ~SPENCER, J. 1974. Puncture sets. J. Combm. Theory A 17, 329-336.Google Scholar
- ~VITTER, J. S. 1984. Faster methods for random sampling. Commun. ACM, 703-718. Google Scholar
- ~WELZL, E. 1988. Partition trees for triangle counting and other range searching problems. In ~Proceedings of the 4th ACM Symposium on Comptuatlonal Geometry. ACM, New York, pp. ~23 33. Google Scholar
Index Terms
- Las Vegas algorithms for linear and integer programming when the dimension is small
Recommendations
A Las Vegas algorithm for linear programming when the dimension is small
SFCS '88: Proceedings of the 29th Annual Symposium on Foundations of Computer ScienceAn 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 ...
Fast parallel algorithms for minimum and related problems with small integer inputs
IPPS '95: Proceedings of the 9th International Symposium on Parallel ProcessingThe fundamental problem of minimum computation has several well studied generalizations such as prefix minima, range minima, and all nearest smaller values computations. Recent papers introduced parallel algorithms for these problems when the n input ...
Fast Integer Sorting in Linear Space
STACS '00: Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer ScienceWe present a fast deterministic algorithm for integer sorting in linear space. Our algorithm sorts n integers in linear space in O(n(log log n)1:5) time. This improves the O(n(log log n)2) time bound given in [11]. This result is obtained by combining ...
Reviews
Joseph M. Lambert
As the title suggests, Clarkson's algorithm is randomized. For a given linear program of n constraints and d variables, the algorithm has an expected running time of O d 2n + log n O d d/2+O 1 +O d 4 n log n . Previous algorithms had expected running times of O 2 2dn and O 3 d2n . The author gives comparable results for integer programming problems. The key idea of the algorithms is random sampling to quickly throw out redundant constraints. The linear programming algorithm actually consists of four linear programming algorithms. One is a simplex-like algorithm. Another is a recursive algorithm that quickly throws away redundant constraints. Actually, it has the effect of building a small constraint set efficiently and at the same time carefully controlling the number of operations. An iterative algorithm is used to weight the constraints so that a small, nonredundant set of constraints can be found quickly and in a controlled number of operations. Finally, a mixed algorithm uses the iterative algorithm to make calls to the recursive algorithm. The paper is important for those interested in computational complexity, and for those who wish to look for fast algorithms for special linear and integer programs. It is extremely well-polished and points to recent work that built upon the ideas presented at a 1988 conference. There are 30 references; none are mere padding.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments