More Web Proxy on the site http://driver.im/

Article

Free access

A subexponential bound for linear programming

Authors:

Jiří Matoušek,

Emo WelzlAuthors Info & Claims

SCG '92: Proceedings of the eighth annual symposium on Computational geometry

Pages 1 - 8

https://doi.org/10.1145/142675.142678

Published: 01 July 1992 Publication History

Abstract

We present a simple randomized algorithm which solves linear programs with n constraints and d variables in expected O(nde^{(d ln(n+1))^1/4}) time in the unit cost model (where we count the number of arithmetic operations on the numbers in the input). The expectation is over the internal randomizations performed by the algorithm, and holds for any input. The algorithm is presented in an abstract framework, which facilitates its application to several other related problems. The algorithm has been presented in a previous work by the authors [ShW], but its analysis and the subexponential complexity bound are new.

References

[1]

F. Behrend, Uber die kleinste umbeschriebene und die grStlte einbeschriebene Ellipse eines konvexen Bereiches, Math. Ann. 115 (1938), 379-411.

[2]

B. Chazelle, An optimal convex hull algorithm and new results on cuttings, in "Proc. 32nd Annum IEEE Symp. on Foundations of Computer Science" (1991), 29-38.

Digital Library

[3]

K.L. Clarkson, Linear programming in O(n3a2) time, Inform. Process. Lett. 22 (1986), 21-24.

Digital Library

[4]

K.L. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small, manuscript, 1989.

[5]

L. Danzer, D. Laugwitz and H. Lenz, /~Iber das LSwnersche Ellipsoid und sein Analogon unter den einem EikSrper eingeschriebenen Ellipsoiden, Arch. Math. 8 (1957), 214-219.

[6]

D.B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, N.J., 1963.

[7]

M.E. Dyer, On a multidimensional search technique and its application to the Euclidean onecenter problem, SIAM J. Comput 15 (1986), 725- 738.

Digital Library

[8]

M.E. Dyer, A class of convex programs with applications to computational geometry, in "Proc. 8th Annual ACM Symp. on Computational Geometry'' (1992), this proceedings.

Digital Library

[9]

M.E. Dyer ~md A. M. Frieze, A randomized algorithm for fixed-dimensional linear programming, manuscript, 1987.

[10]

B. G/irtner, manuscript in preparation, M~rch 1992.

[11]

F. Juhnke, LSwner ellipsoids via semiinfinite optimization and (quasi-) convexity theory, Technische Universit/it Magdeburg, Sektion Mathematik, Report 4/90 (1990).

[12]

H. Jung, 0ber die kleinste Kugel, die eine r/iumhche Figur einschlietlt, J. Reine Angew. Math. 123 (1901), 241-257.

[13]

G. Kalai, A subexponential randomized simplex algorithm, to appear in Proc. ~dth A CM Symposium on Theory of Computing, 1992.

Digital Library

[14]

N. Karmarkar, A new polynomial-time algorithm for linear programming, Gombinatorica 4 (1984), 373-395.

Digital Library

[15]

L.G. Khachiyan, Polynomial algorithm in linear programming, U.S.S.R. Gomput. Math. and Math. Phys. 20 (1980), 53-72.

[16]

V. Klee and G.J. Minty, How good is the simplex algorithm, Inequalities III, pp. 159-175, O. Shisha (ed.) Academic Press, New-York, 1972.

[17]

N. Megiddo, Linear programming in linear time when the dimension is fixed, J. Assoc. Gomput. Mach. 31 (1984), 114-127.

Digital Library

[18]

M. J. Post, Minimum spanning ellipsoids, in "Proc. 16th Annual ACM Symposium on Theory of Computing" (1984), 108-116.

Digital Library

[19]

R. Seidel, Low dimensional linear programming and convex hulls made easy, Discrete Comput. Geom. 6 (1991), 423-434.

Digital Library

[20]

R. Seidel, Backwards analysis of randomized algorithms, manuscript, 1991.

[21]

M. Sharir and E. Welzl, A combinatorial bound for linear programming and related problems, in "Proc. 1992 Symp. on Theoretical Aspects of Computer Science", Lecture Notes in Computer Science 577 (1992), 569-579.

Digital Library

[22]

E. Welzl, Smallest enclosing disks (balls and ellipsoids), in "New Results and New Trends in Computer Science", (H. Maurer, Ed.), Lecture Notes in Computer Science 555 (1991), 359-370.

Cited By

He YQi KFeng XChen R(2024)Load-Balanced and Full-Coverage Beam Layout for Multibeam Satellite Systems2024 6th International Conference on Communications, Signal Processing, and their Applications (ICCSPA)10.1109/ICCSPA61559.2024.10794213(1-5)Online publication date: 8-Jul-2024
https://doi.org/10.1109/ICCSPA61559.2024.10794213
Huiberts SLee YZhang XSaha BServedio R(2023)Upper and Lower Bounds on the Smoothed Complexity of the Simplex MethodProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585124(1904-1917)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585124
Peigney M(2023)Shakedown theorems for shape memory alloys structures with functional fatigue — Application to nitinol stentsInternational Journal of Solids and Structures10.1016/j.ijsolstr.2023.112393280(112393)Online publication date: Sep-2023
https://doi.org/10.1016/j.ijsolstr.2023.112393
Show More Cited By

Recommendations

Improved Deterministic Algorithms for Linear Programming in Low Dimensions
Special Issue on SODA’16 and Regular Papers

Chazelle and Matoušek [J. Algorithms, 1996] presented a derandomization of Clarkson’s sampling-based algorithm [J. ACM, 1995] for solving linear programs with n constraints and d variables in d^(7+o(1))dn deterministic time. The time bound can be ...
Fast and Optimal Parallel Multidimensional Search in PRAMs with Applications to Linear Programming and Related Problems

We describe a deterministic parallel algorithm for linear programming in fixed dimension d that takes poly(log log n) time in the common concurrent read concurrent write (CRCW) PRAM model and does optimal O(n) work. In the exclusive read exclusive write ...
On Interior-Point Warmstarts for Linear and Combinatorial Optimization

Despite the many advantages of interior-point algorithms over active-set methods for linear optimization, one of the remaining practical challenges is their current limitation to efficiently solve series of related problems by an effective warmstarting ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '92: Proceedings of the eighth annual symposium on Computational geometry

July 1992

384 pages

ISBN:0897915178

DOI:10.1145/142675

Chairman:
David Avis

Copyright © 1992 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1992

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SOCG92

Sponsor:

SOCG92: 8th Annual Symposium on Computational Geometry 1992

June 10 - 12, 1992

Berlin, Germany

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

58
Total Citations
View Citations
402
Total Downloads

Downloads (Last 12 months)89
Downloads (Last 6 weeks)12

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

He YQi KFeng XChen R(2024)Load-Balanced and Full-Coverage Beam Layout for Multibeam Satellite Systems2024 6th International Conference on Communications, Signal Processing, and their Applications (ICCSPA)10.1109/ICCSPA61559.2024.10794213(1-5)Online publication date: 8-Jul-2024
https://doi.org/10.1109/ICCSPA61559.2024.10794213
Huiberts SLee YZhang XSaha BServedio R(2023)Upper and Lower Bounds on the Smoothed Complexity of the Simplex MethodProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585124(1904-1917)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585124
Peigney M(2023)Shakedown theorems for shape memory alloys structures with functional fatigue — Application to nitinol stentsInternational Journal of Solids and Structures10.1016/j.ijsolstr.2023.112393280(112393)Online publication date: Sep-2023
https://doi.org/10.1016/j.ijsolstr.2023.112393
Fey FGorlatch S(2021)CPRIC: Collaborative Parallelism for Randomized Incremental Constructions2021 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW52791.2021.00081(490-499)Online publication date: Jun-2021
https://doi.org/10.1109/IPDPSW52791.2021.00081
Avis DFriedmann O(2017)An exponential lower bound for Cunningham's ruleMathematical Programming: Series A and B10.1007/s10107-016-1008-4161:1-2(271-305)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s10107-016-1008-4
Das SNandy ASarvottamananda S(2016)Linear Time Algorithm for 1-Center in $$\mathfrak {R}^d$$ Under Convex Polyhedral Distance FunctionFrontiers in Algorithmics10.1007/978-3-319-39817-4_5(41-52)Online publication date: 27-May-2016
https://doi.org/10.1007/978-3-319-39817-4_5
Gärtner BCheng SDevillers O(2014)Sampling with Removal in LP-type ProblemsProceedings of the thirtieth annual symposium on Computational geometry10.1145/2582112.2582121(511-518)Online publication date: 8-Jun-2014
https://dl.acm.org/doi/10.1145/2582112.2582121
Kalantari B(2014)A characterization theorem and an algorithm for a convex hull problemAnnals of Operations Research10.1007/s10479-014-1707-2226:1(301-349)Online publication date: 24-Aug-2014
https://doi.org/10.1007/s10479-014-1707-2
Sipiran IBustos BSchreck T(2013)Data-aware 3D partitioning for generic shape retrievalComputers and Graphics10.1016/j.cag.2013.04.00237:5(460-472)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.cag.2013.04.002
Sipiran IBustos B(2013)Key-componentsThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-013-0870-929:12(1319-1332)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1007/s00371-013-0870-9
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents