Two algorithms for maximizing a separable concave function over a polymatroid feasible region

Two algorithms for maximizing a separable concave function over a polymatroid feasible region

0.00 Avg rating0 Votes
Article ID: iaor19931992
Country: Netherlands
Volume: 54
Issue: 2
Start Page Number: 227
End Page Number: 236
Publication Date: Sep 1991
Journal: European Journal of Operational Research
Authors:
Keywords: programming: convex
Abstract:

This paper presents two new algorithms for maximizing a separable concave function on a polymatroid. Both algorithms apply to the discrete as well as the continuous version of the problem. The application of these algorithms to several types of polymatroids is discussed, and the paper shows that the Decomposition Algorithm runs in polynomial time (in the discrete version) for network and generalized symmetric polymatroids, and the Bottom Up Algorithm (in the discrete version) runs in polynomial time when the polymatroid is given as an explicit list of constraints.

Reviews

Required fields are marked *. Your email address will not be published.