A polynomial algorithm for resourse allocation problems with polymatroid constrains 1

We investigate the following problem. It is necessary to allocate a discrete resource to a set of activities so as to maximize a separable concave function of a profit over a set of feasible resource allocations formed by integer points of a polymatroid. We present the Dichotomic Greedy Algorithm (DGA) for solving this problem and prove that the running time of DGA is polynomially bounded. The implementation of DGA is discussed for uniform and generalized symmetric polymatroids.