Efficient resource allocation with non-concave objective functions

We consider resource allocation with separable objective functions defined over subranges of the integers. While it is well known that (the maximizati on version of) this problem can be solved efficiently if the objective func tions are concave, the general problem of resource allocation with non-conc ave functions is difficult. In this article we show that for fairly well-sh aped non-concave objective functions, the optimal solution can be computed efficiently. Our main enabling ingredient is an algorithm for aggregating t wo 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 n umber of subintervals that are convex or concave.