IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v35y1988i5p463-472.html
   My bibliography  Save this article

An algorithmic proof of the polyhedral decomposition theorem

Author

Listed:
  • Mustafa Akgül

Abstract

It is well‐known that any point in a convex polyhedron P can be written as the sum of a convex combination of extreme points of P and a non‐negative linear combination of extreme rays of P. Grötschel, Lovász, and Schrijver gave a polynomial algorithm based on the ellipsoidal method to find such a representation for any x in P when P is bounded. Here we show that their algorithm can be modified and implemented in polynomial time using the projection method or a simplex‐type algorithm : in n(2n + 1) simplex pivots, where n is the dimension of x. Extension to the unbounded case is immediate.

Suggested Citation

  • Mustafa Akgül, 1988. "An algorithmic proof of the polyhedral decomposition theorem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 35(5), pages 463-472, October.
    • Handle: RePEc:wly:navres:v:35:y:1988:i:5:p:463-472
    DOI: 10.1002/1520-6750(198810)35:53.0.CO;2-5
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/1520-6750(198810)35:53.0.CO;2-5
    Download Restriction: no
    File URL: https://libkey.io/10.1002/1520-6750(198810)35:53.0.CO;2-5?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
    ---><---

    References listed on IDEAS

    as
    1. Peter B. R. Hazell & Carlos Pomareda, 1981. "Evaluating Price Stabilization Schemes with Mathematical Programming," American Journal of Agricultural Economics, Agricultural and Applied Economics Association, vol. 63(3), pages 550-556.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lambert, David K. & McCarl, Bruce A. & He, Quifen & Kaylen, Michael S. & Rosenthal, Wesley & Chang, Ching-Cheng & Nayda, W.I., 1995. "Uncertain Yields In Sectoral Welfare Analysis: An Application To Global Warming," Journal of Agricultural and Applied Economics, Southern Agricultural Economics Association, vol. 27(2), pages 1-14, December.
    2. McCarl, Bruce A. & Apland, Jeffrey, 1986. "Validation Of Linear Programming Models," Southern Journal of Agricultural Economics, Southern Agricultural Economics Association, vol. 18(2), pages 1-10, December.
    3. McCarl, Bruce A., 1984. "Model Validation: An Overview with some Emphasis on Risk Models," Review of Marketing and Agricultural Economics, Australian Agricultural and Resource Economics Society, vol. 52(03), pages 1-21, December.

    More about this item

    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:wly:navres:v:35:y:1988:i:5:p:463-472. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.