On Properties of Optimal Solutions of Allocation Problems with Polymatroid Feasible Region

We consider the polymatroid allocation problem P. It can be formulated as the problem of maximizing separable concave nondecreasing function over integer points of polymatroid. It is well known that the problem P can be solved by Greedy Algorithm (GA). But the complexity of GA is not polynomially bounded in general because of possibly great number of iterations. Recently several polynomial algorithms for the polymatroid allocation problem were proposed. The best of them are the Scaling Algorithm, the Decomposition Algorithm, and the Dichotomic Algorithm. Among algorithms constructed for special cases of the problem P there are the Conquer Tree Algorithm and the Bottom Up Algorithm. The optimality proofs of all mentioned algorithms used complicated constructions and were very long. We present several new fundamental properties of solutions generated by GA. These properties lead to new optimality proofs for all mentioned algorithms, that are significantly shorter (about 2–3 times) and simpler. On this base it becomes clear that all mentioned algorithms for polymatroid allocation problem are different ways to implement GA efficiently.