{"ID":2847218,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.00470","arxiv_id":"2511.00470","title":"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 is $k$ non-negative submodular functions $f_1,f_2,\\ldots,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,\\ldots,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,\\ldots,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/2$, yielding a $k/2$-approximation algorithm. We also prove a nearly matching lower bound: the integrality gap is at least $k/2-ε$ for any constant $ε\u003e0$ when $k$ is fixed.","short_abstract":"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,\\ldots,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,\\ldots,S_k$ so that $\\sum_{i=1}^k...","url_abs":"https://arxiv.org/abs/2511.00470","url_pdf":"https://arxiv.org/pdf/2511.00470v2","authors":"[\"Ryuhei Mizutani\"]","published":"2025-11-01T09:46:34Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.DM\"]","methods":"[]","has_code":false}