|
 |
Efficient Resource Allocation with Non-Concave Objective Functions
Abstract
We consider resource allocation with separable objective functions defined
over subranges of the integers. While it is well known that (the maximization
version of) this problem can be solved efficiently if the objective functions
are concave, the general problem of resource allocation with non-concave
functions is difficult. In this article we show that for fairly well-shaped
non-concave objective functions, the optimal solution can be computed efficiently.
Our main enabling ingredient is an algorithm for aggregating two objective
functions, where the cost depends on the complexity of the two involved
functions. As a measure of complexity of a function, we use the number of
subintervals that are convex or concave.
- Version 1.0, April 19, 1999, in PDF Format.
(This version was submitted to a journal Feb. 5, 1999.)
|
| |
|
