View PDF HTML (experimental)

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,\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 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.

Submission history

From: Ryuhei Mizutani [view email]
[v1] Sat, 1 Nov 2025 09:46:34 UTC (13 KB)
[v2] Mon, 2 Feb 2026 08:39:42 UTC (14 KB)
[v3] Wed, 16 Sep 2026 10:29:15 UTC (17 KB)