95-03
About Properties of Optimal Solutions of Resource Allocation Problems
by Girlich, E.; Kovalev, M.; Zaporozhets, A.
Preprint series: 95-03, Preprints
- MSC:
- 90C10 Integer programming
Abstract: 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. Onthe base of the solvability of the problem by Greedy Algorithm weestablish several properties of its optimal solutions. By using theseproperties we propose new and short proofs for the validity of some ofthe best known algorithms solving the problem in general and severalspecial cases.
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.