单调子模成本分配的一种近似算法 (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,\ldots,f_k$ on the ground set $N$ given by evaluation oracles, and the goal is to partition $N$ into $k$ (possibly empty) sets $X_1,\ldots,X_k$ so that $\sum_{i=1}^k f_i(X_i)$ is minimized. In this paper, we focus on the case when $f_1,\ldots,f_k$ are monotone (denoted by Mono-MSCA). We provide a natural LP-relaxation for Mono-MSCA, which is equivalent to the convex program relaxation introduced by Chekuri and Ene. We show that the integrality gap of the LP-relaxation is at most $k/2$, which yields a $k/2$-approximation algorithm for Mono-MSCA. We also show that the integrality gap of the LP-relaxation is at least $k/2-ε$ for any constant $ε>0$ when $k$ is fixed.

翻译：本文研究了最小子模成本分配（MSCA）问题。MSCA的输入为定义在基础集$N$上的$k$个非负子模函数$f_1,\ldots,f_k$（通过求值预言机给出），目标是将$N$划分为$k$个（可能为空的）集合$X_1,\ldots,X_k$，以最小化$\sum_{i=1}^k f_i(X_i)$。本文重点关注$f_1,\ldots,f_k$为单调函数的情形（记为Mono-MSCA）。我们为Mono-MSCA提出了一个自然的线性规划松弛，该松弛等价于Chekuri和Ene引入的凸规划松弛。我们证明该线性规划松弛的整数间隙至多为$k/2$，从而为Mono-MSCA提供了一个$k/2$-近似算法。同时，当$k$固定时，对于任意常数$ε>0$，我们证明该线性规划松弛的整数间隙至少为$k/2-ε$。