Zurück zu den Preprints des Jahres 1995


A Polynomial Algorithm for Resource AllocationProblems with Polymatroid Constraints

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

Series: 1995-02, Preprints

90C10 Integer programming

We present the Dichotomic Greedy Algorithm (DGA) for the fol-
lowing resource allocation problem: maximize a separable concave
function of a profit over a set of feasible allocations formed by integer
points of a polymatroid.It is proved that the running time of DGA
is polynomially bounded. The implementation of DGA for several
special types of polymatroid feasible sets is analysed.