95-02

A Polynomial Algorithm for Resource AllocationProblems with Polymatroid Constraints

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

 

Preprint series: 95-02, Preprints

MSC:
90C10 Integer programming

 

Abstract: We present the Dichotomic Greedy Algorithm (DGA) for the fol-lowing resource allocation problem: maximize a separable concavefunction of a profit over a set of feasible allocations formed by integerpoints of a polymatroid.It is proved that the running time of DGAis polynomially bounded. The implementation of DGA for severalspecial types of polymatroid feasible sets is analysed.


The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster