A Polynomial Time Algorithm for the Resource Allocation Problem with a Convex Objective Function |
| |
Authors: | N. Katoh T. Ibaraki H. Mine |
| |
Affiliation: | 1.Department of Applied Mathematics and Physics,Faculty of Engineering, Kyoto University,Kyoto,Japan |
| |
Abstract: | Consider the resource allocation problem:minimize ∑ni=1 fi(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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|