An Approximation Algorithm for Monotone Submodular Cost Allocation

Abstract

In this paper, we consider the minimum submodular cost allocation (MSCA) problem. The input of MSCA consists of $k$ nonnegative 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 facility location problem with submodular facility costs introduced 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/2$, yielding a $k/2$-approximation algorithm. For fixed $k$, we also provide a matching lower bound on the integrality gap and prove a matching hardness result via an approximation preserving reduction from the minimum vertex cover problem in a $k$-partite hypergraph. We further provide applications of our results to the dual linear program of weighted $k$-polymatroid intersection and the minimum-weight $b$-vertex cover problem in a $k$-partite hypergraph.