Minimizing a Monotone Concave Function with Laminar Covering Constraints

Let

V

be a finite set with |

V

|=

n

. A family

$\mathcal{F}\subseteq 2^{V}$

is called

laminar

if for arbitrary two sets

$X, Y \in \mathcal{F}$

,

X

∩

Y

≠ ∅ implies

X

 ⊆ 

Y

or

X

 ⊇ 

Y

. Given a laminar family

$\mathcal{F}$

, a demand function

d

→ℝ

 + 

, and a monotone concave cost function

$F : \mathbb{R}_{+}^{V} \rightarrow \mathbb{R}_{+}$

, we consider the problem of finding a minimum-cost

$x \in \mathbb{R}_{+}^{V}$

such that

x

(

X

)≥

d

(

X

) for all

$X \in \mathcal{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

2

q

) time if

F

can be decomposed into monotone concave functions by the partition of

V

that is induced by the laminar family

$\mathcal{F}$

, where

q

is the time required for the computation of

F

(

x

) for any

$x \in \mathbb{R}_{+}^{V}$

. We also prove that if

F

is given by an oracle, then it takes

${\it \Omega}(n^{2}q)$

time to solve the problem, which implies that our O(

n

2

q

) time algorithm is optimal in this case. Furthermore, we propose an O(

n

log

2

n

) 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

${\it \Omega}(2^{n \over 2}q)$

time when

F

is given implicitly by an oracle, and that it is NP-hard if

F

is given explicitly.