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.
Federgruen, Awi, and H. Groenevelt. "The greedy procedure for resource allocation problems: Necessary and sufficient conditions for optimality." Operations Research 34, no. 6 (1986): 909-918.
Each author name for a Columbia Business School faculty member is linked to a faculty research page, which lists additional publications by that faculty member.
Each topic is linked to an index of publications on that topic.