Minimizing a monotone concave function with laminar covering constraints Original Research Article

Let V be a finite set with image. A family image is called laminar if for all two sets image, image implies image or image. Given a laminar family image, a demand function image, and a monotone concave cost function image, we consider the problem of finding a minimum-cost image such that image for all image. Here we do not assume that the cost function F is differentiable or even continuous. We show that the problem can be solved in image time if F can be decomposed into monotone concave functions by the partition of V that is induced by the laminar family image, where q is the time required for the computation of image for any image. We also prove that if F is given by an oracle, then it takes image time to solve the problem, which implies that our image time algorithm is optimal in this case. Furthermore, we propose an image 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 image time when F is given implicitly by an oracle, and that it is NP-hard if F is given explicitly in a functional form.