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

Awi Federgruen and Henri Groenevelt
Additional contact information
Awi Federgruen: Columbia University, New York, New York
Henri Groenevelt: University of Rochester, Rochester, New York

Operations Research, 1986, vol. 34, issue 6, 909-918

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.

Keywords: 625 integer algorithms; 642 nonlinear algorithms; 650 nonlinear theory (search for similar items in EconPapers)
Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.34.6.909 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:34:y:1986:i:6:p:909-918

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().