An Approximation Algorithm for Monotone Submodular Cost Allocation
Ryuhei Mizutani · 2025
Read An Approximation Algorithm for Monotone Submodular Cost Allocation by Ryuhei Mizutani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-00470.txt.
Introduction
Ryuhei Mizutani studies the minimum submodular cost allocation problem: split a ground set among several agents so the total cost, scored by one submodular function per agent, is as low as possible. Submodular functions capture diminishing returns, and the monotone case matches the facility location problem with submodular facility costs posed by Svitkina and Tardos. Mizutani analyzes a natural linear programming relaxation of the problem.
He shows the relaxation's integrality gap is at most half the number of agents, which yields a matching approximation algorithm with the same guarantee. For a fixed number of agents, a matching lower bound and a hardness result, reduced from vertex cover in multipartite hypergraphs, show the bound is tight. Applications follow for polymatroid intersection duals and minimum-weight vertex cover variants.
Catalog record
| CREATOR | Ryuhei Mizutani |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-00470
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Approximation Algorithm for Monotone Submodular Cost Allocation Ryuhei Mizutani Abstract In this paper, we consider the minimum submodular cost allocation ( MSCA ) problem. The input of MSCA is k k non-negative submodular functions f 1 , … , f k f_{1},\ldots,f_{k} on the ground set N N given by evaluation oracles, and the goal is to partition N N into k k (possibly empty) sets X 1 , … , X k X_{1},\ldots,X_{k} so that ∑ i = 1 k f i ( X i ) \sum_{i=1}^{k}f_{i}(X_{i}) is minimized. In this paper, we focus on the case when f 1 , … , f k 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 k/2 , which yields a k / 2 k/2 -approximation algorithm for Mono-MSCA . We also show that the integrality gap of the LP-relaxation is at least k / 2 − ϵ k/2-\epsilon for any constant ϵ > 0 \epsilon>0 when k k is fixed. 1 Introduction Let N be a finite set of cardinality n , and k\geq 2 a positive integer. A set function f:2^{N}\to\mathbb{R} is called submodular if f(S)+f(T)\geq f(S\cup T)+f(S\cap T) holds for every S,T\subseteq N . In this paper, we focus on the Minimum Submodular Cost Allocation ( MSCA ) problem, introduced by Chekuri and Ene [ 5 ] . The input of MSCA is k non-negative submodular functions f_{1},\ldots,f_{k}:2^{N}\to\mathbb{R}_{+} 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, i.e., \displaystyle\min\left\{\sum_{i=1}^{k}f_{i}(X_{i})\ \middle|\ X_{1},\ldots,X_{k}\ \mathrm{is\ a\ partition\ of\ }N\right\}. Throughout this paper, we assume that the input functions f_{1},\ldots,f_{k} satisfy f_{i}(\emptyset)=0 for each i=1,\ldots,k . Several well-studied problems such as the multiway cut problems in graphs and hypergraphs, the submodular multiway partition problems, and uniform metric labeling can be cast as special cases of MSCA . In the case when all submodular functions are monotone, MSCA is equivalent to the submodular facility location problem considered by Svitkina and Tardos [ 18 ] . In this paper, we focus on this setting, i.e., the case where each of f_{1},\ldots,f_{k} is monotone submodular. We denote MSCA with monotone submodular functions f_{1},\ldots,f_{k} by Mono-MSCA . The aim of this paper is to investigate the integrality gap of a natural LP-relaxation for Mono-MSCA when k is small. LP-relaxation. To provide an LP-relaxation for Mono-MSCA , we introduce some notation. Let \mathbf{1}\in\mathbb{Z}^{N}_{>0} denote the all-ones vector and [k]:=\{1,2,\ldots,k\} . For any S\subseteq N , let \chi_{S}\in\{0,1\}^{N} denote the characteristic vector of S . We consider the following linear programming relaxation for MSCA : \displaystyle(\textsc{LP-Rel})\ \ \ \ \ \mathrm{minimize} \displaystyle\ \ \ \sum_{S\subseteq N,i\in[k]}y_{i}(S)f_{i}(S) \displaystyle\mathrm{subject\ to} \displaystyle\ \ \ y_{i}\in\mathbb{R}^{2^{N}}_{+}\ \mathrm{for\ every\ }i\in[k], \displaystyle\ \ \ \sum_{S\subseteq N,i\in[k]}y_{i}(S)\chi_{S}=\mathbf{1}. In this LP-relaxation, we interpret y_{i}(S)=1 to mean that the set S is assigned to f_{i} in MSCA , whereas y_{i}(S)=0 means that S is not assigned to f_{i} . We note that if an integer feasible solution (y_{1},\ldots,y_{k}) satisfies y_{i}(S_{1})=y_{i}(S_{2})=1 for two distinct sets S_{1},S_{2}\subseteq N and i\in[k] , then by the submodularity of f_{i} we can update y_{i}(S_{1}):=y_{i}(S_{2}):=0 and y_{i}(S_{1}\cup S_{2}):=1 without increasing the objective value. Hence, after such uncrossing operations, any integer feasible solution to LP-Rel induces a partition of N for MSCA . The linear program LP-Rel is equivalent to the convex program relaxation introduced by Chekuri and Ene [ 5 ] (see Appendix A for details). The linear program LP-Rel can also be seen as the dual linear program of the unweighted k -polymatroid intersection (see [ 16 ] and Appendix B for details). Regarding the integrality gap of LP-Rel , Ene and Vondrák [ 8 ] showed that if \mathrm{P}\neq\mathrm{NP} , then the integrality gap of LP-Rel for general submodular functions cannot be upper-bounded by any factor. Hence, it is natural to focus on special cases such as a monotone case that admit a bounded integrality gap. We refer to LP-Rel restricted to monotone submodular functions f_{1},\ldots,f_{k} as Mono-LP-Rel . Svitkina and Tardos [ 18 ] gave a (1+\ln n) -approximation algorithm for Mono-MSCA , and Chekuri and Ene [ 5 ] showed that the integrality gap of Mono-LP-Rel is at most (1+\ln n) . Santiago and Shepherd [ 15 ] gave a k -approximation algorithm for Mono-MSCA and showed that the integrality gap of Mono-LP-Rel is at most k . On the negative side, Svitkina and Tardos [ 18 ] showed that the set cover problem with a collection of k sets can be reduced to Mono-MSCA . This implies that if k is a part of input, Mono-MSCA cannot be approximated within a factor of (1-o(1))\cdot\ln n [ 10 ] , which matches the approximation ratio shown by Svitkina and Tardos [ 18 ] . On the other hand, if k\leq\log n , then the set cover problem with a collection of k sets can be solved in time polynomial in n by brute-force. Hence, in this case the reduction does not yield any approximation lower bound for Mono-MSCA . Therefore, the approximability of Mono-MSCA and the integrality gap of Mono-LP-Rel for small k are much less understood. In this paper, we aim to obtain tight upper and lower bounds of the integrality gap of Mono-LP-Rel when k is small. Our results and techniques. As mentioned previously, the current best upper bound on the integrality gap of Mono-LP-Rel is \min\{k,1+\ln n\} . Our first result improves this to k/2 . Theorem 1.1 . The integrality gap of Mono-LP-Rel is at most k/2 . When k=2 , Mono-LP-Rel coincides with the dual linear program of the unweighted polymatroid intersection. Hence, when k=2 , Theorem 1.1 corresponds to the (total) dual integrality of the polymatroid intersection. Since the proof of Theorem 1.1 is constructive, it yields a k/2 -approximation algorithm for Mono-MSCA , which improves the current best approximation ratio \min\{k,1+\ln n\} . Theorem 1.2 . There exists a k/2 -approximation algorithm for Mono-MSCA . Our next result is a lower bound on the integrality gap of Mono-LP-Rel , which is tight when k is fixed. Theorem 1.3 . If \log n\geq k , then the integrality gap of Mono-LP-Rel is at least \frac{k}{2}-\frac{k(k-1)}{\log n} . We note that if k is fixed, Theorem 1.3 implies that the integrality gap of Mono-LP-Rel is at least k/2-\epsilon for any constant \epsilon>0 , which matches the upper bound in Theorem 1.1 . Another consequence is that if k\leq\sqrt{\log n} , then the lower bound in Theorem 1.3 satisfies \frac{k}{2}-\frac{k(k-1)}{\log n}\geq\frac{k}{2}-1 , which almost matches the upper bound k/2 in Theorem 1.1 . Our proof of Theorem 1.1 is constructive as follows. We first obtain an optimal solution (y_{1},\ldots,y_{k}) to Mono-LP-Rel whose supports are chains via the ellipsoid method. Then, we take the top 2/k of a fraction of the largest sets in the chains. We show that such a collection of sets can be partitioned into groups of k sets, each of which has union N . The existence of this partition implies that the