Zurück zu den Preprints des Jahres 1995


About Properties of Optimal Solutions of Resource Allocation Problems

by Girlich, E., Kovalev, M., Zaporozhets, A..

Series: 1995-03, Preprints

90C10 Integer programming

We consider the problem of maximizing a separable concave non-
decreasing function over integer points of a polymatroid feasible re-
gion known as an important case of resource allocation problems. On
the base of the solvability of the problem by Greedy Algorithm we
establish several properties of its optimal solutions. By using these
properties we propose new and short proofs for the validity of some of
the best known algorithms solving the problem in general and several
special cases.