Minimizing a monotone concave function with laminar covering constraints

Let V be a finite set with |V|=n. A family [email protected]?2^V is called laminar if for all two sets X,[email protected]?F, [email protected]?Y @A implies [email protected]?Y or [email protected]?Y. Given a laminar family F, a demand function d:F->R"+, and a monotone concave cost function F:R"+^V->R"+, we consider the problem of finding a minimum-cost [email protected]?R"+^V such that x(X)>=d(X) for all [email protected]?F. Here we do not assume that the cost function F is differentiable or even continuous. We show that the problem can be solved in O(n^2q) time if F can be decomposed into monotone concave functions by the partition of V that is induced by the laminar family F, where q is the time required for the computation of F(x) for any [email protected]?R"+^V. We also prove that if F is given by an oracle, then it takes @W(n^2q) time to solve the problem, which implies that our O(n^2q) time algorithm is optimal in this case. Furthermore, we propose an O(nlog^2n) algorithm if F is the sum of linear cost functions with fixed setup costs. These also make improvements in complexity results for source location and edge-connectivity augmentation problems in undirected networks. Finally, we show that in general our problem requires @W(2^n^/^2q) time when F is given implicitly by an oracle, and that it is NP-hard if F is given explicitly in a functional form.