2 ALGORITHMS FOR MAXIMIZING A SEPARABLE CONCAVE FUNCTION OVER A POLYMATROID FEASIBLE REGION

In this paper we present 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 we show 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.