An Approximation Algorithm for Monotone Submodular Cost Allocation

In this paper, we consider the minimum submodular cost allocation (MSCA) problem. The input of MSCA is $k$ non-negative submodular functions $f_1,f_2,\dots ,f_k$ on the ground set $N$ given by evaluation oracles, and the goal is to partition $N$ into $k$ (possibly empty) sets $S_1,S_2,\dots ,S_k$ so that ${\sum }_{i=1}^k{f}_i(S_i)$ is minimized. In this paper, we focus on the case when $f_1,f_2,\dots ,f_k$ are monotone, which coincides with the submodular facility location problem considered by Svitkina and Tardos. We show that the integrality gap of a natural LP-relaxation for MSCA with monotone submodular functions is at most $k\mathrm{/}2$, yielding a $k\mathrm{/}2$-approximation algorithm. We also prove a nearly matching lower bound: the integrality gap is at least $k\mathrm{/}2-\epsilon$ for any constant $\epsilon >0$ when $k$ is fixed.