A short proof of optimality of the Bottom Up algorithm for discrete resource allocation problems

The paper deals with the problem of maximizing a separable concave function over integer points of a polymatroid, known to be the integer case of the resource allocation problem. The Bottom Up algorithm for the case when the polymatroid is specified by an explicit list of constraints was presented by H. Groenevelt. We give a new proof of optimality of the Bottom Up algorithm. It is considerably shorter and simpler than the original proof. Our proof is based on the analysis of the greedy algorithm for this problem and properties of greedy solutions.