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.

Authors
Awi Federgruen and Henri Groenevelt
Format
Journal Article
Publication Date
Journal
Operations Research

Full Citation

Federgruen, Awi and Henri Groenevelt
. “The greedy procedure for resource allocation problems: Necessary and sufficient conditions for optimality.”
Operations Research
vol.
34
, (January 01, 1986):
909
-
918
.