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.