Zurück zu den Preprints des Jahres 1995


1995-02

A Polynomial Algorithm for Resource AllocationProblems with Polymatroid Constraints

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


Series: 1995-02, Preprints

MSC:
90C10 Integer programming

Abstract:
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.

Keywords: