article

Free access

Las Vegas algorithms for linear and integer programming when the dimension is small

Author:

Kenneth L. ClarksonAuthors Info & Claims

Journal of the ACM (JACM), Volume 42, Issue 2

Pages 488 - 499

https://doi.org/10.1145/201019.201036

Published: 01 March 1995 Publication History

PDF eReader

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(d²n) + (log n)O(d)^d/2+O(1) + O(d⁴√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(2^d dn + 8^dd√n ln ln n) + d^O(d)φ ln n operations on numbers with d^O(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 E^d has the same time bound.

References

[1]

~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

[2]

~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

[3]

~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.

Crossref

Google Scholar

[4]

~BELL, D. E. 1977. A theorem concerning the integer lattice. Stud. Appl. Math. 56, 187-188.

Google Scholar

[5]

~CHARNES, A. 1952. Optimality and degeneracy in linear programming. Econometrika 20, 160-170.

Google Scholar

[6]

~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.

Crossref

Google Scholar

[7]

CLARKSON, K. L. 1986. Linear programming in O(n3a2) time. bzf. Proc. Lett. 22, 21-24.

Crossref

Google Scholar

[8]

CLARKSON, K. L. 1987. New applications of random sampling in computational geometry. Disc. ~Comput. Geometry 2, 195-222.

Google Scholar

[9]

~CLARKSON, m. L., AND SHOR, P. W. 1989. Applications of random sampling in computational ~geometry, II. Disc. Comput. Geometry 4, 387-421.

Crossref

Google Scholar

[10]

~DYER, M. E. 1986. On a multidimensional search technique and its application to the euclidean ~one-centre problem. SIAM J. Comput. 15, 725-738.

Crossref

Google Scholar

[11]

~DYER, M. E., AND FRIEZE. A. M. 1989. A randomized algorithm for fixed-dimensional linear ~programming. Math. Prog. 44, 203-212.

Crossref

Google Scholar

[12]

~FLIT, S. D. 1984. A fast algorithm for the two-variable integer programming problem. J. ACM, ~99-113.

Crossref

Google Scholar

[13]

~FRANK, A., AND TARDOS, 12. 1987. An application of simultaneous approximation in combinato- ~rial optimization. Combinatorica 7, 49-66.

Crossref

Google Scholar

[14]

~GILL, P. E., MURRAY, W., AND WRIGHT, M. H. 1981. Practical Optimtzatton. Academic Press, ~Orlando, Fla.

Google Scholar

[15]

~GILL, P. E., MURRAY, W., AND WRIGHT, M. H. 1991. Numerical Linear Algebra and Optimization. ~Addison-Wesley, New York.

Google Scholar

[16]

~HAUSSLER, D., AND WELZL, E. 1987. Epsilon-nets and simplex range queries. Dtsc. Comput. ~Geometry 2, 127-151.

Google Scholar

[17]

~KALAI, G. 1992. A subexponential randomized simplex algorithm. In Proceedings of the 24th ~Annual. ACM Symposium on the Theory of Computing.

Crossref

Google Scholar

[18]

~KANNAN, R. 1987. Minkowski's convex body theorem and integer programming. Math. Oper. ~Res. 12, 415-440.

Crossref

Google Scholar

[19]

~KHACHIAN, L. G. 1980. Polynomial algorithms in linear programming, Z. Vych. Math. Mat. Fiz., ~53-72.

Google Scholar

[20]

~KLEE, g., AND MINTY, G. J. 1972. HOW good is the simplex algorithm? In Inequalities III. ~Academic Press, Orlando, Fla.

Google Scholar

[21]

~LENSTRA, H. W. 1983. Integer programming with a fixed number of variables. Math. Oper. Res., ~538-548.

Google Scholar

[22]

~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.

Crossref

Google Scholar

[23]

~MEGIDDO, N. 1984. Linear programming in linear time when the dimension is fixed. J. ACM31, ~114-127.

Crossref

Google Scholar

[24]

~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.

Crossref

Google Scholar

[25]

~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

[26]

~SCHRIJVER, A. 1986. Theory of Linear and Integer Programmb~g. Wiley, New York.

Crossref

Google Scholar

[27]

~SEIDEL, R. 199l. Small-dimensional linear programming and convex hulls made easy. Disc. ~Comput. Geom. 6, 5, 423-433.

Crossref

Google Scholar

[28]

~SPENCER, J. 1974. Puncture sets. J. Combm. Theory A 17, 329-336.

Google Scholar

[29]

~VITTER, J. S. 1984. Faster methods for random sampling. Commun. ACM, 703-718.

Crossref

Google Scholar

[30]

~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.

Crossref

Google Scholar

Cited By

View all

Gutiérrez-Soto CGaldames PPalomino M(2024)An Efficient Probabilistic Algorithm to Detect Periodic Patterns in Spatio-Temporal DatasetsBig Data and Cognitive Computing10.3390/bdcc80600598:6(59)Online publication date: 3-Jun-2024
https://doi.org/10.3390/bdcc8060059
Aanjaneya MNagarakatte S(2024)Maximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear Programs with Convex Hull as the Intermediate RepresentationProceedings of the ACM on Programming Languages10.1145/36564278:PLDI(1239-1263)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656427
Ghadiri MLee YPadmanabhan SSwartworth WWoodruff DYe GMohar BShinkar IO'Donnell R(2024)Improving the Bit Complexity of Communication for Distributed Convex OptimizationProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649787(1130-1140)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649787
Show More Cited By

Index Terms

Las Vegas algorithms for linear and integer programming when the dimension is small
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
      2. Mixed discrete-continuous optimization
        Integer programming
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
      2. Mixed discrete-continuous optimization
        Integer programming

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 Science

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 ...
Fast parallel algorithms for minimum and related problems with small integer inputs
IPPS '95: Proceedings of the 9th International Symposium on Parallel Processing

The 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 Science

We 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)²) time bound given in [11]. This result is obtained by combining ...

Reviews

Reviewer: 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 42, Issue 2

March 1995

250 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/201019

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1995

Published in JACM Volume 42, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

177
Total Citations
View Citations
1,906
Total Downloads

Downloads (Last 12 months)244
Downloads (Last 6 weeks)39

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gutiérrez-Soto CGaldames PPalomino M(2024)An Efficient Probabilistic Algorithm to Detect Periodic Patterns in Spatio-Temporal DatasetsBig Data and Cognitive Computing10.3390/bdcc80600598:6(59)Online publication date: 3-Jun-2024
https://doi.org/10.3390/bdcc8060059
Aanjaneya MNagarakatte S(2024)Maximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear Programs with Convex Hull as the Intermediate RepresentationProceedings of the ACM on Programming Languages10.1145/36564278:PLDI(1239-1263)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656427
Ghadiri MLee YPadmanabhan SSwartworth WWoodruff DYe GMohar BShinkar IO'Donnell R(2024)Improving the Bit Complexity of Communication for Distributed Convex OptimizationProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649787(1130-1140)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649787
Jansen KRohwedder L(2023)On Integer Programming, Discrepancy, and ConvolutionMathematics of Operations Research10.1287/moor.2022.130848:3(1481-1495)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1287/moor.2022.1308
Uddin RMahin MRajan PRavishankar CTsotras V(2023)Dwell Regions: Generalized Stay Regions for Streaming and Archival Trajectory DataACM Transactions on Spatial Algorithms and Systems10.1145/35438509:2(1-35)Online publication date: 12-Apr-2023
https://dl.acm.org/doi/10.1145/3543850
Ducoffe G(2023)Distance problems within Helly graphs and k-Helly graphsTheoretical Computer Science10.1016/j.tcs.2023.113690946:COnline publication date: 10-Feb-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.113690
Chamanbaz MBouffanais R(2023)A sequential deep learning algorithm for sampled mixed-integer optimisation problemsInformation Sciences: an International Journal10.1016/j.ins.2023.03.061634:C(73-84)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1016/j.ins.2023.03.061
Shen YXiao JPimentel AGrosser TLee K(2022)TCPS: a task and cache-aware partitioned scheduler for hard real-time multi-core systemsProceedings of the 23rd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3519941.3535067(37-49)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3519941.3535067
Aanjaneya MLim JNagarakatte SJhala RDillig I(2022)Progressive polynomial approximations for fast correctly rounded math librariesProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523447(552-565)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523447
Chen CHong ZJiang J(2022)Scheduling in Real-Time Mobile SystemsACM Transactions on Embedded Computing Systems10.1145/351774721:3(1-36)Online publication date: 28-May-2022
https://dl.acm.org/doi/10.1145/3517747
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

A Las Vegas algorithm for linear programming when the dimension is small

Fast parallel algorithms for minimum and related problems with small integer inputs

Fast Integer Sorting in Linear Space

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations