article

A new polynomial-time algorithm for linear programming

Author:

N. KarmarkarAuthors Info & Claims

Combinatorica, Volume 4, Issue 4

Pages 373 - 395

https://doi.org/10.1007/BF02579150

Published: 01 December 1984 Publication History

Abstract

No abstract available.

Cited By

View all

Karimi MTunçel L(2025)Efficient Implementation of Interior-Point Methods for Quantum Relative EntropyINFORMS Journal on Computing10.1287/ijoc.2024.057037:1(3-21)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1287/ijoc.2024.0570
Poursoltani MDelage EGeorghiou ASalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Robust data-driven prescriptiveness optimizationProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693734(40982-40999)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693734
Wang SDelage E(2024)A Column Generation Scheme for Distributionally Robust Multi-Item Newsvendor ProblemsINFORMS Journal on Computing10.1287/ijoc.2022.001036:3(849-867)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1287/ijoc.2022.0010
Show More Cited By

Index Terms

Recommendations

On linear programming relaxations for solving polynomial programming problems
Highlights
- Theoretically compared the tightness of the J-set relaxation with the recursive McCormick relaxations.
Abstract
This paper studies linear programming (LP) relaxations for solving polynomial programming problems. A polynomial programming problem can be equivalently formulated as a quadratically constrained quadratic program (QCQP) by introducing ...
New Branch-and-Cut Algorithm for Bilevel Linear Programming

Linear mixed 0---1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP) problems. We exploit these equivalences to transpose the concept of mixed 0---1 Gomory cuts to BLP. The first phase of our new ...
A polynomial-time algorithm, based on Newton's method, for linear programming

A new interior method for linear programming is presented and a polynomial time bound for it is proven. The proof is substantially different from those given for the ellipsoid algorithm and for Karmarkar's algorithm. Also, the algorithm is conceptually ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Combinatorica Volume 4, Issue 4

Dec. 1984

23 pages

ISSN:0209-9683

Editor:
L. Lovász
Eo¨tvo¨s Univ., Budapest, Hungary

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 December 1984

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

706
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Karimi MTunçel L(2025)Efficient Implementation of Interior-Point Methods for Quantum Relative EntropyINFORMS Journal on Computing10.1287/ijoc.2024.057037:1(3-21)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1287/ijoc.2024.0570
Poursoltani MDelage EGeorghiou ASalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Robust data-driven prescriptiveness optimizationProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693734(40982-40999)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693734
Wang SDelage E(2024)A Column Generation Scheme for Distributionally Robust Multi-Item Newsvendor ProblemsINFORMS Journal on Computing10.1287/ijoc.2022.001036:3(849-867)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1287/ijoc.2022.0010
Dadush DKoh ZNatura BOlver NVégh LMohar BShinkar IO'Donnell R(2024)A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or ColumnProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649764(1561-1572)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649764
Ramesh MImeson FFidan BSmith S(2024)Anytime Replanning of Robot Coverage Paths for Partially Unknown EnvironmentsIEEE Transactions on Robotics10.1109/TRO.2024.345441740(4190-4206)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TRO.2024.3454417
De Pellegrini FGupta VAzouzi RGueye SRichier CLeguay J(2024)Fair Coflow Scheduling via Controlled SlowdownIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.344618835:12(2347-2360)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1109/TPDS.2024.3446188
Liu HWang TLang CFeng SJin YLi Y(2024)GLANPattern Recognition10.1016/j.patcog.2024.110694155:COnline publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1016/j.patcog.2024.110694
Raza NMoazeni F(2024)Chance-constrained vulnerability assessment of smart water distribution systems against stealthy false data injection attacksInternational Journal of Critical Infrastructure Protection10.1016/j.ijcip.2023.10064544:COnline publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1016/j.ijcip.2023.100645
Mariz JBadiozamani MPeroni RSilva R(2024)A critical review of bench aggregation and mining cut clustering techniques based on optimization and artificial intelligence to enhance the open-pit mine planningEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.108334133:PDOnline publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.engappai.2024.108334
Li HHuang WDuan ZMguni DShao KWang JDeng X(2024)A survey on algorithms for Nash equilibria in finite normal-form gamesComputer Science Review10.1016/j.cosrev.2023.10061351:COnline publication date: 25-Jun-2024
https://dl.acm.org/doi/10.1016/j.cosrev.2023.100613
Show More Cited By

Abstract

Cited By

Index Terms

Recommendations

On linear programming relaxations for solving polynomial programming problems

New Branch-and-Cut Algorithm for Bilevel Linear Programming

A polynomial-time algorithm, based on Newton's method, for linear programming

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations