A Polynomial Time Algorithm for the Resource Allocation Problem with a Convex Objective Function
Naoki Katoh, Toshihide Ibaraki, Hisashi Mine · Journal of the Operational Research Society · 1979
Consider the resource allocation problem:minimize ∑ni=1fi(xi) subject to ∑ni=1 xi = N and xi's being nonnegative integers, where each fi is a convex function. The well-known algorithm based on the incremental method requires O(N log n + n) time to solve this problem. We propose here a new algorithm based on the Lagrange multiplier method, requiring O[n2(log N)2] time. The latter is faster if N is much larger than n. Such a situation occurs, for example, when the optimal sample size problem related to monitoring the urban air pollution is treated.