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

The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality

Author

Listed:
  • Awi Federgruen

    (Columbia University, New York, New York)

  • Henri Groenevelt

    (University of Rochester, Rochester, New York)

Abstract

In many resource allocation problems, the objective is to allocate discrete resource units to a set of activities so as to maximize a concave objective function subject to upper bounds on the total amounts allotted to certain groups of activities. If the constraints determine a polymatroid and the objective is linear, it is well known that the greedy procedure results in an optimal solution. In this paper we extend this result to objectives that are “weakly concave,” a property generalizing separable concavity. We exhibit large classes of models for which the set of feasible solutions is a polymatroid and for which efficient implementations of the greedy procedure can be given.

Suggested Citation

  • Awi Federgruen & Henri Groenevelt, 1986. "The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality," Operations Research, INFORMS, vol. 34(6), pages 909-918, December.
    • Handle: RePEc:inm:oropre:v:34:y:1986:i:6:p:909-918
    DOI: 10.1287/opre.34.6.909
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.34.6.909
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.34.6.909?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. Jan A. Van Mieghem & Nils Rudi, 2002. "Newsvendor Networks: Inventory Management and Capacity Investment with Discretionary Activities," Manufacturing & Service Operations Management, INFORMS, vol. 4(4), pages 313-335, August.
    2. Simai He & Jiawei Zhang & Shuzhong Zhang, 2012. "Polymatroid Optimization, Submodularity, and Joint Replenishment Games," Operations Research, INFORMS, vol. 60(1), pages 128-137, February.
    3. Aksin, O. Zeynep & Harker, Patrick T., 2003. "Capacity sizing in the presence of a common shared resource: Dimensioning an inbound call center," European Journal of Operational Research, Elsevier, vol. 147(3), pages 464-483, June.
    4. Dorit Hochbaum, 2007. "Complexity and algorithms for nonlinear optimization problems," Annals of Operations Research, Springer, vol. 153(1), pages 257-296, September.
    5. Aleksandar Pekeč, 1997. "Optimization under ordinal scales: When is a greedy solution optimal?," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 46(2), pages 229-239, June.
    6. Harris, Shannon L. & May, Jerrold H. & Vargas, Luis G. & Foster, Krista M., 2020. "The effect of cancelled appointments on outpatient clinic operations," European Journal of Operational Research, Elsevier, vol. 284(3), pages 847-860.
    7. Hyun-soo Ahn & Mehmet Gümüş & Philip Kaminsky, 2007. "Pricing and Manufacturing Decisions When Demand Is a Function of Prices in Multiple Periods," Operations Research, INFORMS, vol. 55(6), pages 1039-1057, December.
    8. Pinto, Roberto, 2016. "Stock rationing under a profit satisficing objective," Omega, Elsevier, vol. 65(C), pages 55-68.
    9. Rohit Patel & Can Urgun, 2021. "Costly Inspection and Money Burning in Internal Capital Markets," Working Papers 2021-29, Princeton University. Economics Department..
    10. Niederhoff, Julie A., 2007. "Using separable programming to solve the multi-product multiple ex-ante constraint newsvendor problem and extensions," European Journal of Operational Research, Elsevier, vol. 176(2), pages 941-955, January.
    11. Awi Federgruen & C. Daniel Guetta & Garud Iyengar, 2018. "Two‐echelon distribution systems with random demands and storage constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 65(8), pages 594-618, December.
    12. S. Viswanathan, 2007. "An Algorithm for Determining the Best Lower Bound for the Stochastic Joint Replenishment Problem," Operations Research, INFORMS, vol. 55(5), pages 992-996, October.
    13. Awi Federgruen & Nan Yang, 2008. "Selecting a Portfolio of Suppliers Under Demand and Supply Risks," Operations Research, INFORMS, vol. 56(4), pages 916-936, August.
    14. Renato de Matta & Vernon Ning Hsu & Timothy J. Lowe, 1999. "The selection allocation problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(6), pages 707-725, September.

    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:34:y:1986:i:6:p:909-918. 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.