IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v29y1981i6p1039-1091.html
   My bibliography  Save this article

Feature Article—The Ellipsoid Method: A Survey

Author

Listed:
  • Robert G. Bland

    (Cornell University, Ithaca, New York)

  • Donald Goldfarb

    (Cornell University, Ithaca, New York)

  • Michael J. Todd

    (Cornell University, Ithaca, New York)

Abstract

In February 1979 a note by L. G. Khachiyan indicated how an ellipsoid method for linear programming can be implemented in polynomial time. This result has caused great excitement and stimulated a flood of technical papers. Ordinarily there would be no need for a survey of work so recent, but the current circumstances are obviously exceptional. Word of Khachiyan's result has spread extraordinarily fast, much faster than comprehension of its significance. A variety of issues have, in general, not been well understood, including the exact character of the ellipsoid method and of Khachiyans result on polynomiality, its practical significance in linear programming, its implementation, its potential applicability to problems outside of the domain of linear programming, and its relationship to earlier work. Our aim is to help clarify these important issues in the context of a survey of the ellipsoid method, its historical antecedents, recent developments, and current research.

Suggested Citation

  • Robert G. Bland & Donald Goldfarb & Michael J. Todd, 1981. "Feature Article—The Ellipsoid Method: A Survey," Operations Research, INFORMS, vol. 29(6), pages 1039-1091, December.
    • Handle: RePEc:inm:oropre:v:29:y:1981:i:6:p:1039-1091
    DOI: 10.1287/opre.29.6.1039
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.29.6.1039
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.29.6.1039?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Robert M. Freund & Jorge R. Vera, 2009. "Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 869-879, November.
    2. Maxime C. Cohen & Ilan Lobel & Renato Paes Leme, 2020. "Feature-Based Dynamic Pricing," Management Science, INFORMS, vol. 66(11), pages 4921-4943, November.
    3. Yaguang Yang, 2013. "A Polynomial Arc-Search Interior-Point Algorithm for Linear Programming," Journal of Optimization Theory and Applications, Springer, vol. 158(3), pages 859-873, September.
    4. Paul Karaenke & Martin Bichler & Stefan Minner, 2019. "Coordination Is Hard: Electronic Auction Mechanisms for Increased Efficiency in Transportation Logistics," Management Science, INFORMS, vol. 65(12), pages 5884-5900, December.
    5. Tanaka, Masato & Matsui, Tomomi, 2022. "Pseudo polynomial size LP formulation for calculating the least core value of weighted voting games," Mathematical Social Sciences, Elsevier, vol. 115(C), pages 47-51.
    6. V. Balakrishnan & R. L. Kashyap, 1999. "Robust Stability and Performance Analysis of Uncertain Systems Using Linear Matrix Inequalities," Journal of Optimization Theory and Applications, Springer, vol. 100(3), pages 457-478, March.
    7. K. A. Ariyawansa & P. L. Jiang, 2000. "On Complexity of the Translational-Cut Algorithm for Convex Minimax Problems," Journal of Optimization Theory and Applications, Springer, vol. 107(2), pages 223-243, November.
    8. Simone A. Rocha & Thiago G. Mattos & Rodrigo T. N. Cardoso & Eduardo G. Silveira, 2022. "Applying Artificial Neural Networks and Nonlinear Optimization Techniques to Fault Location in Transmission Lines—Statistical Analysis," Energies, MDPI, vol. 15(11), pages 1-24, June.
    9. Zhang, Yufeng & Khani, Alireza, 2019. "An algorithm for reliable shortest path problem with travel time correlations," Transportation Research Part B: Methodological, Elsevier, vol. 121(C), pages 92-113.

    More about this item

    Keywords

    660 ellipsoid method;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:29:y:1981:i:6:p:1039-1091. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.