An Approximation Algorithm for Monotone Submodular Cost Allocation
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908804174577664 |
|---|---|
| author | Mizutani, Ryuhei |
| author_facet | Mizutani, Ryuhei |
| contents | 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 $ε>0$ when $k$ is fixed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_00470 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Approximation Algorithm for Monotone Submodular Cost Allocation Mizutani, Ryuhei Data Structures and Algorithms Discrete Mathematics 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 $ε>0$ when $k$ is fixed. |
| title | An Approximation Algorithm for Monotone Submodular Cost Allocation |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2511.00470 |