article

Free access

Accelerating LP algorithms

Author:

B. L. FoxAuthors Info & Claims

Communications of the ACM, Volume 12, Issue 7

Pages 384 - 385

https://doi.org/10.1145/363156.363169

Published: 01 July 1969 Publication History

PDF eReader

Abstract

It is shown how a novel method for computing (related) inner products can accelerate the pricing phase of LP algorithms. Other LP applications are indicated.

References

[1]

DENARDO, E. V., AND Fox, B.L. Multichain Markov renewal programs. SIAM J. Appl. Math. I6 (1968), 468-487.

Crossref

Google Scholar

[2]

SIMONNARD, M. Linear Programming. Prentice-Hall, Englewood Cliffs, N. J., 1966.

Google Scholar

[3]

WINOGRAD, S. A new algorithm for inner product. IEEE Trans. C-17 (1968), 693-694.

Google Scholar

Cited By

View all

Fox B(1978)Data Structures and Computer Science Techniques in Operations ResearchOperations Research10.1287/opre.26.5.68626:5(686-717)Online publication date: 1-Oct-1978
https://dl.acm.org/doi/10.1287/opre.26.5.686
Fox B(1973)Reducing the number of multiplikations in iterative processesActa Informatica10.1007/BF002886513:1(43-45)Online publication date: 1-Mar-1973
https://dl.acm.org/doi/10.1007/BF00288651
Brent R(1970)Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identityNumerische Mathematik10.1007/BF0230886716:2(145-156)Online publication date: 1-Nov-1970
https://dl.acm.org/doi/10.1007/BF02308867

Index Terms

Accelerating LP algorithms
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Linear programming

Recommendations

Approximate Constraint Satisfaction Requires Large LP Relaxations

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are no more powerful than programs ...
Hybrid-LP

The simplex method has proven its efficiency in practice for linear programming (LP) problems of various types and sizes. However, its theoretical worst-case complexity in addition to its poor performance for very large-scale LP problems has driven ...
Hypergraphic LP Relaxations for Steiner Trees

In this paper we prove new properties of hypergraphic linear programming relaxations for the Steiner tree problem. In particular, we show that a partition-based relaxation has the same value as other relaxations based on subtours and directed cuts. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 12, Issue 7

July 1969

86 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/363156

Editor:
M. Stuart Lynn
IBM Scientific Center, Houston, TX

Issue’s Table of Contents

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1969

Published in CACM Volume 12, Issue 7

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
392
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)8

Reflects downloads up to 28 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Fox B(1978)Data Structures and Computer Science Techniques in Operations ResearchOperations Research10.1287/opre.26.5.68626:5(686-717)Online publication date: 1-Oct-1978
https://dl.acm.org/doi/10.1287/opre.26.5.686
Fox B(1973)Reducing the number of multiplikations in iterative processesActa Informatica10.1007/BF002886513:1(43-45)Online publication date: 1-Mar-1973
https://dl.acm.org/doi/10.1007/BF00288651
Brent R(1970)Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identityNumerische Mathematik10.1007/BF0230886716:2(145-156)Online publication date: 1-Nov-1970
https://dl.acm.org/doi/10.1007/BF02308867

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

Approximate Constraint Satisfaction Requires Large LP Relaxations

Hybrid-LP

Hypergraphic LP Relaxations for Steiner Trees

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

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