2511/2511.00470.md

Title: An Approximation Algorithm for Monotone Submodular Cost Allocation

URL Source: https://arxiv.org/html/2511.00470

Markdown Content: 1Introduction 2Approximation algorithm 3Lower bound on the integrality gap An Approximation Algorithm for Monotone Submodular Cost Allocation Ryuhei Mizutani Faculty of Science and Technology, Keio University, Kanagawa, 223-8522, Japan. E-mail: mizutani@math.keio.ac.jp Abstract

In this paper, we consider the minimum submodular cost allocation (MSCA) problem. The input of MSCA is 𝑘 non-negative submodular functions 𝑓 1 , … , 𝑓 𝑘 on the ground set 𝑁 given by evaluation oracles, and the goal is to partition 𝑁 into 𝑘 (possibly empty) sets 𝑋 1 , … , 𝑋 𝑘 so that ∑ 𝑖

1 𝑘 𝑓 𝑖 ​ ( 𝑋 𝑖 ) is minimized. In this paper, we focus on the case when 𝑓 1 , … , 𝑓 𝑘 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 𝑘 / 2 , which yields a 𝑘 / 2 -approximation algorithm for Mono-MSCA. We also show that the integrality gap of the LP-relaxation is at least 𝑘 / 2 − 𝜖 for any constant 𝜖

0 when 𝑘 is fixed.

1Introduction

Let 𝑁 be a finite set of cardinality 𝑛 , and 𝑘 ≥ 2 a positive integer. A set function 𝑓 : 2 𝑁 → ℝ is called submodular if 𝑓 ​ ( 𝑆 ) + 𝑓 ​ ( 𝑇 ) ≥ 𝑓 ​ ( 𝑆 ∪ 𝑇 ) + 𝑓 ​ ( 𝑆 ∩ 𝑇 ) holds for every 𝑆 , 𝑇 ⊆ 𝑁 . In this paper, we focus on the Minimum Submodular Cost Allocation (MSCA) problem, introduced by Chekuri and Ene [5]. The input of MSCA is 𝑘 non-negative submodular functions 𝑓 1 , … , 𝑓 𝑘 : 2 𝑁 → ℝ + given by evaluation oracles, and the goal is to partition 𝑁 into 𝑘 (possibly empty) sets 𝑋 1 , … , 𝑋 𝑘 so that ∑ 𝑖

1 𝑘 𝑓 𝑖 ​ ( 𝑋 𝑖 ) is minimized, i.e.,

min ⁡ { ∑ 𝑖

1 𝑘 𝑓 𝑖 ​ ( 𝑋 𝑖 ) | 𝑋 1 , … , 𝑋 𝑘 ​ is ​ a ​ partition ​ of ​ 𝑁 } .

Throughout this paper, we assume that the input functions 𝑓 1 , … , 𝑓 𝑘 satisfy 𝑓 𝑖 ​ ( ∅ )

0 for each 𝑖

1 , … , 𝑘 . 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 𝑓 1 , … , 𝑓 𝑘 is monotone submodular. We denote MSCA with monotone submodular functions 𝑓 1 , … , 𝑓 𝑘 by Mono-MSCA. The aim of this paper is to investigate the integrality gap of a natural LP-relaxation for Mono-MSCA when 𝑘 is small.

LP-relaxation.

To provide an LP-relaxation for Mono-MSCA, we introduce some notation. Let 𝟏 ∈ ℤ

0 𝑁 denote the all-ones vector and [ 𝑘 ] := { 1 , 2 , … , 𝑘 } . For any 𝑆 ⊆ 𝑁 , let 𝜒 𝑆 ∈ { 0 , 1 } 𝑁 denote the characteristic vector of 𝑆 . We consider the following linear programming relaxation for MSCA:

( LP-Rel ) minimize
∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 )

subject ​ to
𝑦 𝑖 ∈ ℝ + 2 𝑁 ​ for ​ every ​ 𝑖 ∈ [ 𝑘 ] ,

∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ​ ( 𝑆 ) ​ 𝜒 𝑆

𝟏 .

In this LP-relaxation, we interpret 𝑦 𝑖 ​ ( 𝑆 )

1 to mean that the set 𝑆 is assigned to 𝑓 𝑖 in MSCA, whereas 𝑦 𝑖 ​ ( 𝑆 )

0 means that 𝑆 is not assigned to 𝑓 𝑖 . We note that if an integer feasible solution ( 𝑦 1 , … , 𝑦 𝑘 ) satisfies 𝑦 𝑖 ​ ( 𝑆 1 )

𝑦 𝑖 ​ ( 𝑆 2 )

1 for two distinct sets 𝑆 1 , 𝑆 2 ⊆ 𝑁 and 𝑖 ∈ [ 𝑘 ] , then by the submodularity of 𝑓 𝑖 we can update 𝑦 𝑖 ​ ( 𝑆 1 ) := 𝑦 𝑖 ​ ( 𝑆 2 ) := 0 and 𝑦 𝑖 ​ ( 𝑆 1 ∪ 𝑆 2 ) := 1 without increasing the objective value. Hence, after such uncrossing operations, any integer feasible solution to LP-Rel induces a partition of 𝑁 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 𝑘 -polymatroid intersection (see [16] and Appendix B for details). Regarding the integrality gap of LP-Rel, Ene and Vondrák [8] showed that if P ≠ 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 𝑓 1 , … , 𝑓 𝑘 as Mono-LP-Rel. Svitkina and Tardos [18] gave a ( 1 + ln ⁡ 𝑛 ) -approximation algorithm for Mono-MSCA, and Chekuri and Ene [5] showed that the integrality gap of Mono-LP-Rel is at most ( 1 + ln ⁡ 𝑛 ) . Santiago and Shepherd [15] gave a 𝑘 -approximation algorithm for Mono-MSCA and showed that the integrality gap of Mono-LP-Rel is at most 𝑘 . On the negative side, Svitkina and Tardos [18] showed that the set cover problem with a collection of 𝑘 sets can be reduced to Mono-MSCA. This implies that if 𝑘 is a part of input, Mono-MSCA cannot be approximated within a factor of ( 1 − 𝑜 ​ ( 1 ) ) ⋅ ln ⁡ 𝑛 [10], which matches the approximation ratio shown by Svitkina and Tardos [18]. On the other hand, if 𝑘 ≤ log ⁡ 𝑛 , then the set cover problem with a collection of 𝑘 sets can be solved in time polynomial in 𝑛 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 𝑘 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 𝑘 is small.

Our results and techniques.

As mentioned previously, the current best upper bound on the integrality gap of Mono-LP-Rel is min ⁡ { 𝑘 , 1 + ln ⁡ 𝑛 } . Our first result improves this to 𝑘 / 2 .

Theorem 1.1.

The integrality gap of Mono-LP-Rel is at most 𝑘 / 2 .

When 𝑘

2 , Mono-LP-Rel coincides with the dual linear program of the unweighted polymatroid intersection. Hence, when 𝑘

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 𝑘 / 2 -approximation algorithm for Mono-MSCA, which improves the current best approximation ratio min ⁡ { 𝑘 , 1 + ln ⁡ 𝑛 } .

Theorem 1.2.

There exists a 𝑘 / 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 𝑘 is fixed.

Theorem 1.3.

If log ⁡ 𝑛 ≥ 𝑘 , then the integrality gap of Mono-LP-Rel is at least 𝑘 2 − 𝑘 ​ ( 𝑘 − 1 ) log ⁡ 𝑛 .

We note that if 𝑘 is fixed, Theorem 1.3 implies that the integrality gap of Mono-LP-Rel is at least 𝑘 / 2 − 𝜖 for any constant 𝜖

0 , which matches the upper bound in Theorem 1.1. Another consequence is that if 𝑘 ≤ log ⁡ 𝑛 , then the lower bound in Theorem 1.3 satisfies 𝑘 2 − 𝑘 ​ ( 𝑘 − 1 ) log ⁡ 𝑛 ≥ 𝑘 2 − 1 , which almost matches the upper bound 𝑘 / 2 in Theorem 1.1.

Our proof of Theorem 1.1 is constructive as follows. We first obtain an optimal solution ( 𝑦 1 , … , 𝑦 𝑘 ) to Mono-LP-Rel whose supports are chains via the ellipsoid method. Then, we take the top 2 / 𝑘 of a fraction of the largest sets in the chains. We show that such a collection of sets can be partitioned into groups of 𝑘 sets, each of which has union 𝑁 . The existence of this partition implies that the integrality gap of Mono-LP-Rel is at most 𝑘 / 2 . In the proof of Theorem 1.3, we construct 𝑘 monotone submodular functions such that the integrality gap of Mono-LP-Rel is at least 𝑘 2 − 𝑘 ​ ( 𝑘 − 1 ) log ⁡ 𝑛 .

Related work.

Recently, Bi et al. [3] considered the monotone submodular multiway partition problem (Mono-Sub-MP), which is a special case of Mono-MSCA. They showed that Mono-Sub-MP admits a 4 / 3 -approximation, and does not admit a ( 10 / 9 − 𝜖 ) -approximation for every constant 𝜖

0 . For further recent works related to submodular partition problems, see [1, 2, 4, 11, 14].

There are several recent works related to MSCA. Etesami [9] showed that multi-item welfare maximization under network externalities can be formulated as a special case of MSCA. Deng et al. [7] introduced the generalized load-balancing (GLB) problem, and showed that GLB is equivalent to MSCA when the outer norm is the ℓ 1 -norm.

Organization.

The rest of the paper is organized as follows. In Section 2, we show that the integrality gap of Mono-LP-Rel is at most 𝑘 / 2 , which yields a 𝑘 / 2 -approximation algorithm for Mono-MSCA. In Section 3, we show that the integrality gap of Mono-LP-Rel is at least 𝑘 2 − 𝑘 ​ ( 𝑘 − 1 ) log ⁡ 𝑛 when log ⁡ 𝑛 ≥ 𝑘 .

2Approximation algorithm

In this section, we show that the integrality gap of Mono-LP-Rel is at most 𝑘 / 2 , which yields a 𝑘 / 2 -approximation algorithm for Mono-MSCA.

Let 𝑁 be a finite set of cardinality 𝑛 , and 𝑘 ≥ 2 a positive integer. For each 𝑖 ∈ [ 𝑘 ] , let 𝑓 𝑖 : 2 𝑁 → ℝ + be a monotone submodular function with 𝑓 𝑖 ​ ( ∅ )

0 . Recall that Mono-LP-Rel is defined as follows:

( Mono-LP-Rel ) minimize
∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 )

subject ​ to
𝑦 𝑖 ∈ ℝ + 2 𝑁 ​ for ​ every ​ 𝑖 ∈ [ 𝑘 ] ,

∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ​ ( 𝑆 ) ​ 𝜒 𝑆

𝟏 .

To prove the upper bound of the integrality gap, we show that an integer solution to Mono-LP-Rel achieving a 𝑘 / 2 -approximation can be constructed from an optimal solution to Mono-LP-Rel. Since the coefficient matrix of the constraints in Mono-LP-Rel is rational, Mono-LP-Rel has a rational optimal solution ( 𝑦 1 ∗ , … , 𝑦 𝑘 ∗ ) . Let ℒ 𝑖 := { 𝑆 ⊆ 𝑁 ∣ 𝑦 𝑖 ∗ ​ ( 𝑆 )

0 } and 𝑑 𝑖 := | ℒ 𝑖 | for each 𝑖 ∈ [ 𝑘 ] . By the uncrossing operations, we may assume that ℒ 𝑖 is a chain for each 𝑖 ∈ [ 𝑘 ] . Let 𝐶 𝑖 1 ⊋ 𝐶 𝑖 2 ⊋ ⋯ ⊋ 𝐶 𝑖 𝑑 𝑖 be the members of ℒ 𝑖 for each 𝑖 ∈ [ 𝑘 ] . Let 𝑀 be the product of 𝑘 ​ ( 𝑘 − 1 ) and the denominators of 𝑦 𝑖 ∗ ​ ( 𝐶 𝑖 𝑗 ) for all 𝑖 , 𝑗 . Then, 𝑀 ⋅ 𝑦 𝑖 ∗ is an integer vector for every 𝑖 ∈ [ 𝑘 ] . For each 𝑖 ∈ [ 𝑘 ] and 𝑗 ∈ [ 𝑀 ] , define 𝑈 𝑖 𝑗 ⊆ 𝑁 as follows:

𝑈 𝑖 𝑗 := { 𝐶 𝑖 ℓ
if ​ 1 + ∑ 𝑝

1 ℓ − 1 𝑀 ⋅ 𝑦 𝑖 ∗ ​ ( 𝐶 𝑖 𝑝 ) ≤ 𝑗 ≤ ∑ 𝑝

1 ℓ 𝑀 ⋅ 𝑦 𝑖 ∗ ​ ( 𝐶 𝑖 𝑝 ) ​ for ​ some ​ ℓ ∈ [ 𝑑 𝑖 ] ,

∅
if ​ 1 + ∑ 𝑝

1 𝑑 𝑖 𝑀 ⋅ 𝑦 𝑖 ∗ ​ ( 𝐶 𝑖 𝑝 ) ≤ 𝑗 ≤ 𝑀 .

Intuitively, for each 𝑖 ∈ [ 𝑘 ] , we consider the multiset that contains 𝑀 ⋅ 𝑦 𝑖 ∗ ​ ( 𝐶 𝑖 ℓ ) copies of 𝐶 𝑖 ℓ for all ℓ ∈ [ 𝑑 𝑖 ] , and 𝑈 𝑖 𝑗 is the 𝑗 -th largest set in the multiset for each 𝑗 ∈ [ 𝑀 ] . By the definition of 𝑈 𝑖 𝑗 , we have the following lemma.

Lemma 2.1.

For each 𝑖 ∈ [ 𝑘 ] and ℓ

1 , … , 𝑑 𝑖 , the number of 𝑗 ∈ [ 𝑀 ] with 𝑈 𝑖 𝑗

𝐶 𝑖 ℓ is 𝑀 ⋅ 𝑦 𝑖 ∗ ​ ( 𝐶 𝑖 ℓ ) .

We now aim to construct an integer solution to Mono-LP-Rel (i.e., a partition of 𝑁 ) from 𝑈 𝑖 𝑗 s that achieves 𝑘 / 2 -approximation. To this end, we prepare the following two lemmas.

Lemma 2.2.

We have

∑ 𝑖 ∈ [ 𝑘 ] , 𝑗 ∈ [ 𝑀 ] 1 𝑀 ​ 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑗 )

∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ∗ ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 ) .

Proof.

By Lemma 2.1, we have

∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ∗ ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 )

∑ 𝑆 ∈ ℒ 𝑖 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ∗ ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 )

∑ 1 ≤ ℓ ≤ 𝑑 𝑖 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ∗ ​ ( 𝐶 𝑖 ℓ ) ​ 𝑓 𝑖 ​ ( 𝐶 𝑖 ℓ )

∑ 1 ≤ ℓ ≤ 𝑑 𝑖 , 𝑖 ∈ [ 𝑘 ] 1 𝑀 ​ | { 𝑗 ∈ [ 𝑀 ] | 𝑈 𝑖 𝑗

𝐶 𝑖 ℓ } | ⋅ 𝑓 𝑖 ​ ( 𝐶 𝑖 ℓ )

∑ 𝑖 ∈ [ 𝑘 ] , 𝑗 ∈ [ 𝑀 ]

𝑈 𝑖 𝑗

𝐶 𝑖 ℓ ​ for ​ some ​ 1 ≤ ℓ ≤ 𝑑 𝑖 1 𝑀 ​ 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑗 )

∑ 𝑖 ∈ [ 𝑘 ] , 𝑗 ∈ [ 𝑀 ] 1 𝑀 ​ 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑗 ) .

The last equality follows since if 𝑈 𝑖 𝑗 ≠ 𝐶 𝑖 ℓ for all ℓ

1 , … , 𝑑 𝑖 , then we have 𝑈 𝑖 𝑗

∅ by the definition. ∎

Lemma 2.3.

Let 𝑎 1 , … , 𝑎 𝑘 ∈ [ 𝑀 ] be positive integers such that ∑ 𝑖

1 𝑘 𝑎 𝑖 ≤ 𝑀 + 𝑘 − 1 . Then, ⋃ 𝑖

1 𝑘 𝑈 𝑖 𝑎 𝑖

𝑁 .

Proof.

Suppose to the contrary that ⋃ 𝑖

1 𝑘 𝑈 𝑖 𝑎 𝑖 ≠ 𝑁 . Then, there exists 𝑒 ∈ 𝑁 such that 𝑒 ∉ 𝑈 𝑖 𝑎 𝑖 for every 𝑖 ∈ [ 𝑘 ] . Combined with 𝑈 𝑖 1 ⊇ 𝑈 𝑖 2 ⊇ ⋯ ⊇ 𝑈 𝑖 𝑀 for each 𝑖 ∈ [ 𝑘 ] , this implies 𝑒 ∉ 𝑈 𝑖 𝑗 for every 𝑖 ∈ [ 𝑘 ] and integer 𝑗 with 𝑎 𝑖 ≤ 𝑗 ≤ 𝑀 . Hence, by Lemma 2.1 we have

∑ 𝑆 ⊆ 𝑁 , 𝑒 ∈ 𝑆

𝑖 ∈ [ 𝑘 ] 𝑀 ⋅ 𝑦 𝑖 ∗ ​ ( 𝑆 )

∑ 𝑆 ∈ ℒ 𝑖 , 𝑒 ∈ 𝑆

𝑖 ∈ [ 𝑘 ] 𝑀 ⋅ 𝑦 𝑖 ∗ ​ ( 𝑆 )

∑ 1 ≤ ℓ ≤ 𝑑 𝑖 , 𝑒 ∈ 𝐶 𝑖 ℓ

𝑖 ∈ [ 𝑘 ] 𝑀 ⋅ 𝑦 𝑖 ∗ ​ ( 𝐶 𝑖 ℓ )

∑ 1 ≤ ℓ ≤ 𝑑 𝑖 , 𝑒 ∈ 𝐶 𝑖 ℓ

𝑖 ∈ [ 𝑘 ] | { 𝑗 ∈ [ 𝑀 ] | 𝑈 𝑖 𝑗

𝐶 𝑖 ℓ } |

∑ 𝑖 ∈ [ 𝑘 ] | { 𝑗 ∈ [ 𝑀 ] | 𝑈 𝑖 𝑗

𝐶 𝑖 ℓ ​ for ​ some ​ ℓ ∈ [ 𝑑 𝑖 ] , 𝑒 ∈ 𝑈 𝑖 𝑗 } |

≤ ∑ 𝑖 ∈ [ 𝑘 ] | { 𝑗 ∈ [ 𝑎 𝑖 − 1 ] | 𝑈 𝑖 𝑗

𝐶 𝑖 ℓ ​ for ​ some ​ ℓ ∈ [ 𝑑 𝑖 ] } |

≤ ∑ 𝑖 ∈ [ 𝑘 ] ( 𝑎 𝑖 − 1 ) ≤ 𝑀 − 1 .

(2.1)

Since 𝑦 1 ∗ , … , 𝑦 𝑘 ∗ is a feasible solution to Mono-LP-Rel, we have

∑ 𝑆 ⊆ 𝑁 , 𝑒 ∈ 𝑆

𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ∗ ​ ( 𝑆 )

1 .

This implies

∑ 𝑆 ⊆ 𝑁 , 𝑒 ∈ 𝑆

𝑖 ∈ [ 𝑘 ] 𝑀 ⋅ 𝑦 𝑖 ∗ ​ ( 𝑆 )

𝑀 ,

which contradicts the inequality (2). ∎

Since 𝑀 is divisible by 𝑘 ​ ( 𝑘 − 1 ) , we can denote 𝑀

𝑘 ​ ( 𝑘 − 1 ) ⋅ 𝑚 for some integer 𝑚 . For 𝑘 positive integers 𝑎 1 , … , 𝑎 𝑘 ∈ [ 𝑀 ] , we say that an ordered tuple ( 𝑎 1 , … , 𝑎 𝑘 ) covers 𝑁 if ⋃ 𝑖

1 𝑘 𝑈 𝑖 𝑎 𝑖

𝑁 . We show that if there exist distinct 𝑀 ⋅ 2 / 𝑘

2 ​ 𝑚 ​ ( 𝑘 − 1 ) ordered tuples covering 𝑁 , then one of them corresponds to an integer solution to Mono-LP-Rel that achieves 𝑘 / 2 -approximation.

Lemma 2.4.

Suppose that there exist 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ordered tuples

( 𝑎 1 1 , … , 𝑎 𝑘 1 ) , ( 𝑎 1 2 , … , 𝑎 𝑘 2 ) , … , ( 𝑎 1 2 ​ 𝑚 ​ ( 𝑘 − 1 ) , … , 𝑎 𝑘 2 ​ 𝑚 ​ ( 𝑘 − 1 ) )

such that

(1)

𝑎 𝑖 𝑗 ∈ [ 𝑀 ] for each 𝑖 ∈ [ 𝑘 ] and 𝑗 ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] ,

(2)

𝑎 𝑖 𝑗 ≠ 𝑎 𝑖 ℓ for each 𝑖 ∈ [ 𝑘 ] and 𝑗 , ℓ ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] with 𝑗 ≠ ℓ ,

(3)

each ordered tuple covers 𝑁 .

Then, the integrality gap of Mono-LP-Rel is at most 𝑘 / 2 .

Proof.

By Lemma 2.2, we have

∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ∗ ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 )

∑ 𝑖 ∈ [ 𝑘 ] , 𝑗 ∈ [ 𝑀 ] 1 𝑀 ​ 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑗 ) ≥ ∑ 𝑖 ∈ [ 𝑘 ] , 𝑗 ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] 1 𝑀 ​ 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑎 𝑖 𝑗 )

≥ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) 𝑀 ⋅ min ⁡ { ∑ 𝑖 ∈ [ 𝑘 ] 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑎 𝑖 𝑗 ) | 𝑗 ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] }

2 𝑘 ⋅ min ⁡ { ∑ 𝑖 ∈ [ 𝑘 ] 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑎 𝑖 𝑗 ) | 𝑗 ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] } .

(2.2)

The first inequality follows since by the monotonicity of 𝑓 𝑖 , we have 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑗 ) ≥ 𝑓 𝑖 ​ ( ∅ )

0 for every 𝑖 ∈ [ 𝑘 ] and 𝑗 ∈ [ 𝑀 ] . Let

𝑗 ∗ := argmin 𝑗 ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] ​ ∑ 𝑖 ∈ [ 𝑘 ] 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑎 𝑖 𝑗 ) .

Then, by (2) we have

∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ∗ ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 ) ≥ 2 𝑘 ​ ∑ 𝑖 ∈ [ 𝑘 ] 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑎 𝑖 𝑗 ∗ ) .

Hence, we have

𝑘 2 ⋅ ∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ∗ ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 ) ≥ ∑ 𝑖 ∈ [ 𝑘 ] 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑎 𝑖 𝑗 ∗ ) .

(2.3)

Since ⋃ 𝑖

1 𝑘 𝑈 𝑖 𝑎 𝑖 𝑗 ∗

𝑁 , there exists a partition 𝑈 1 , … , 𝑈 𝑘 of 𝑁 such that 𝑈 𝑖 ⊆ 𝑈 𝑖 𝑎 𝑖 𝑗 ∗ for every 𝑖 ∈ [ 𝑘 ] . Then, by (2.3) and the monotonicity of 𝑓 𝑖 , we have

𝑘 2 ⋅ ∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ∗ ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 ) ≥ ∑ 𝑖 ∈ [ 𝑘 ] 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑎 𝑖 𝑗 ∗ ) ≥ ∑ 𝑖 ∈ [ 𝑘 ] 𝑓 𝑖 ​ ( 𝑈 𝑖 ) .

This implies that the integrality gap of Mono-LP-Rel is at most 𝑘 / 2 . ∎

We are now ready to prove Theorem 1.1.

Theorem 1.1.

By Lemma 2.4, it suffices to show that there exist 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ordered tuples satisfying the conditions in Lemma 2.4. For each positive integer 𝑎 ∈ ℤ

0 , define mod ​ ( 𝑎 ) as follows:

mod ​ ( 𝑎 ) := { 𝑟

if 𝑎 ≡ 𝑟 ( mod 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ) for some 𝑟 ∈ [ 2 𝑚 ( 𝑘 − 1 ) − 1 ] ,

2 ​ 𝑚 ​ ( 𝑘 − 1 )

if ​ 𝑎 ≡ 0 ( mod 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ) .

For each 𝑖 ∈ [ 𝑘 ] and 𝑗 ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] , define 𝑎 𝑖 𝑗 as follows:

𝑎 𝑖 𝑗 := { mod ​ ( 2 ​ 𝑚 ​ ( 𝑖 − 1 ) + 𝑗 )

if ​ 1 ≤ 𝑖 ≤ 𝑘 − 1 ,

mod ​ ( ( 2 ​ 𝑚 − 𝑗 + 1 ) ​ ( 𝑘 − 1 ) ) − ⌊ 𝑗 − 1 2 ​ 𝑚 ⌋
if ​ 𝑖

𝑘 .

We show that ( 𝑎 𝑖 𝑗 ) 𝑖 ∈ [ 𝑘 ] , 𝑗 ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] satisfies conditions (1)–(3) in Lemma 2.4. For condition (1), we show that 1 ≤ 𝑎 𝑖 𝑗 ≤ 𝑀 for each 𝑖 ∈ [ 𝑘 ] and 𝑗 ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] . If 1 ≤ 𝑖 ≤ 𝑘 − 1 , then we have

1 ≤ 𝑎 𝑖 𝑗

mod ​ ( 2 ​ 𝑚 ​ ( 𝑖 − 1 ) + 𝑗 ) ≤ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ≤ 𝑘 ​ 𝑚 ​ ( 𝑘 − 1 )

𝑀 .

If 𝑖

𝑘 , then we have

𝑎 𝑖 𝑗

mod ​ ( ( 2 ​ 𝑚 − 𝑗 + 1 ) ​ ( 𝑘 − 1 ) ) − ⌊ 𝑗 − 1 2 ​ 𝑚 ⌋ .

Since ( 2 ​ 𝑚 − 𝑗 + 1 ) ​ ( 𝑘 − 1 ) is a multiple of 𝑘 − 1 , we have

mod ​ ( ( 2 ​ 𝑚 − 𝑗 + 1 ) ​ ( 𝑘 − 1 ) )

𝑝 ​ ( 𝑘 − 1 )

for some positive integer 𝑝 . This implies

mod ​ ( ( 2 ​ 𝑚 − 𝑗 + 1 ) ​ ( 𝑘 − 1 ) ) ≥ 𝑘 − 1 .

Hence, we have

1

𝑘 − 1 − ( 𝑘 − 2 )

𝑘 − 1 − ⌊ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) − 1 2 ​ 𝑚 ⌋ ≤ mod ​ ( ( 2 ​ 𝑚 − 𝑗 + 1 ) ​ ( 𝑘 − 1 ) ) − ⌊ 𝑗 − 1 2 ​ 𝑚 ⌋ ,

and

mod ​ ( ( 2 ​ 𝑚 − 𝑗 + 1 ) ​ ( 𝑘 − 1 ) ) − ⌊ 𝑗 − 1 2 ​ 𝑚 ⌋ ≤ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ≤ 𝑘 ​ 𝑚 ​ ( 𝑘 − 1 )

𝑀 .

Therefore, condition (1) holds for ( 𝑎 𝑖 𝑗 ) 𝑖 ∈ [ 𝑘 ] , 𝑗 ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] .

For condition (2), we next show that 𝑎 𝑖 𝑗 ≠ 𝑎 𝑖 ℓ for each 𝑖 ∈ [ 𝑘 ] and 𝑗 , ℓ ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] with 𝑗 ≠ ℓ . If 1 ≤ 𝑖 ≤ 𝑘 − 1 , then by the definition of 𝑎 𝑖 𝑗 , it is clear that 𝑎 𝑖 𝑗 ≠ 𝑎 𝑖 ℓ holds for each 𝑗 , ℓ ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] with 𝑗 ≠ ℓ . Consider the case when 𝑖

𝑘 . Suppose to the contrary that 𝑎 𝑘 𝑗

𝑎 𝑘 ℓ holds for some 𝑗 , ℓ ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] with 𝑗 ≠ ℓ . This implies that

mod ​ ( ( 2 ​ 𝑚 − 𝑗 + 1 ) ​ ( 𝑘 − 1 ) ) − ⌊ 𝑗 − 1 2 ​ 𝑚 ⌋

mod ​ ( ( 2 ​ 𝑚 − ℓ + 1 ) ​ ( 𝑘 − 1 ) ) − ⌊ ℓ − 1 2 ​ 𝑚 ⌋ .

(2.4)

Since mod ​ ( ( 2 ​ 𝑚 − 𝑗 + 1 ) ​ ( 𝑘 − 1 ) ) and mod ​ ( ( 2 ​ 𝑚 − ℓ + 1 ) ​ ( 𝑘 − 1 ) ) are multiples of 𝑘 − 1 , it follows that

⌊ 𝑗 − 1 2 ​ 𝑚 ⌋ − ⌊ ℓ − 1 2 ​ 𝑚 ⌋

is a multiple of 𝑘 − 1 by (2.4). Combined with

0 ≤ ⌊ 𝑗 − 1 2 ​ 𝑚 ⌋ , ⌊ ℓ − 1 2 ​ 𝑚 ⌋ ≤ 𝑘 − 2 ,

this implies that

⌊ 𝑗 − 1 2 ​ 𝑚 ⌋

⌊ ℓ − 1 2 ​ 𝑚 ⌋ .

Hence, we have 2 ​ 𝑚 ​ ( 𝑝 − 1 ) + 1 ≤ 𝑗 , ℓ ≤ 2 ​ 𝑚 ​ 𝑝 for some 𝑝 ∈ [ 𝑘 − 1 ] . Let 𝑗 ′ := 2 ​ 𝑚 ​ 𝑝 − 𝑗 and ℓ ′ := 2 ​ 𝑚 ​ 𝑝 − ℓ . By the definition of 𝑝 , we have 0 ≤ 𝑗 ′ , ℓ ′ ≤ 2 ​ 𝑚 − 1 . By (2.4), we have

mod ​ ( ( 2 ​ 𝑚 − 𝑗 + 1 ) ​ ( 𝑘 − 1 ) )

mod ​ ( ( 2 ​ 𝑚 − ℓ + 1 ) ​ ( 𝑘 − 1 ) ) .

(2.5)

We also have

mod ​ ( ( 2 ​ 𝑚 − 𝑗 + 1 ) ​ ( 𝑘 − 1 ) )

mod ​ ( ( 2 ​ 𝑚 − 2 ​ 𝑚 ​ 𝑝 + 𝑗 ′ + 1 ) ​ ( 𝑘 − 1 ) )

( 𝑗 ′ + 1 ) ​ ( 𝑘 − 1 ) ,

mod ​ ( ( 2 ​ 𝑚 − ℓ + 1 ) ​ ( 𝑘 − 1 ) )

mod ​ ( ( 2 ​ 𝑚 − 2 ​ 𝑚 ​ 𝑝 + ℓ ′ + 1 ) ​ ( 𝑘 − 1 ) )

( ℓ ′ + 1 ) ​ ( 𝑘 − 1 ) .

(2.6)

Hence, by (2.5) and (2) we have

( 𝑗 ′ + 1 ) ​ ( 𝑘 − 1 )

( ℓ ′ + 1 ) ​ ( 𝑘 − 1 ) .

This implies 𝑗 ′

ℓ ′ , which contradicts 𝑗 ≠ ℓ .

For condition (3), we show that ⋃ 𝑖

1 𝑘 𝑈 𝑖 𝑎 𝑖 𝑗

𝑁 holds for every 𝑗 ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] . By Lemma 2.3, it suffices to show that ∑ 𝑖

1 𝑘 𝑎 𝑖 𝑗 ≤ 𝑀 + 𝑘 − 1 for every 𝑗 ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] . Take any 𝑗 ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] . Let 𝑝 ∈ [ 𝑘 − 1 ] be the unique positive integer such that 2 ​ 𝑚 ​ ( 𝑝 − 1 ) + 1 ≤ 𝑗 ≤ 2 ​ 𝑚 ​ 𝑝 . Let 𝑗 ′ := 2 ​ 𝑚 ​ 𝑝 − 𝑗 . Then, we have 0 ≤ 𝑗 ′ ≤ 2 ​ 𝑚 − 1 . By the definition of 𝑎 𝑖 𝑗 , we have

∑ 𝑖

1 𝑘 𝑎 𝑖 𝑗

∑ 𝑖

1 𝑘 − 1 mod ​ ( 2 ​ 𝑚 ​ ( 𝑖 − 1 ) + 𝑗 ) + mod ​ ( ( 2 ​ 𝑚 − 𝑗 + 1 ) ​ ( 𝑘 − 1 ) ) − ⌊ 𝑗 − 1 2 ​ 𝑚 ⌋

∑ 𝑖

1 𝑘 − 1 mod ​ ( 2 ​ 𝑚 ​ ( 𝑖 − 1 ) + 2 ​ 𝑚 ​ 𝑝 − 𝑗 ′ ) + mod ​ ( ( 2 ​ 𝑚 − 2 ​ 𝑚 ​ 𝑝 + 𝑗 ′ + 1 ) ​ ( 𝑘 − 1 ) ) − ⌊ 2 ​ 𝑚 ​ 𝑝 − 𝑗 ′ − 1 2 ​ 𝑚 ⌋

∑ 𝑖

1 𝑘 − 𝑝 ( 2 ​ 𝑚 ​ ( 𝑖 − 1 ) + 2 ​ 𝑚 ​ 𝑝 − 𝑗 ′ ) + ∑ 𝑖

𝑘 − 𝑝 + 1 𝑘 − 1 ( 2 ​ 𝑚 ​ ( 𝑖 − 1 ) + 2 ​ 𝑚 ​ 𝑝 − 𝑗 ′ − 2 ​ 𝑚 ​ ( 𝑘 − 1 ) )

+ ( 𝑗 ′ + 1 ) ​ ( 𝑘 − 1 ) − ( 𝑝 − 1 )

∑ 𝑖

1 𝑘 − 1 ( 2 ​ 𝑚 ​ ( 𝑖 − 1 ) + 2 ​ 𝑚 ​ 𝑝 − 𝑗 ′ ) − 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ​ ( 𝑝 − 1 ) + ( 𝑗 ′ + 1 ) ​ ( 𝑘 − 1 ) − ( 𝑝 − 1 )

𝑚 ​ 𝑘 ​ ( 𝑘 − 1 ) − ( 𝑘 − 1 ) ​ ( 2 ​ 𝑚 − 2 ​ 𝑚 ​ 𝑝 + 𝑗 ′ ) − 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ​ ( 𝑝 − 1 ) + ( 𝑗 ′ + 1 ) ​ ( 𝑘 − 1 ) − ( 𝑝 − 1 )

𝑀 + 𝑘 − 𝑝 ≤ 𝑀 + 𝑘 − 1 .

This completes the proof. ∎

The proof of Theorem 1.1 provides the construction of a 𝑘 / 2 -approximate integer solution to Mono-LP-Rel. We prove Theorem 1.2 by showing that such an integer solution can be constructed in polynomial time.

Theorem 1.2.

We can obtain a rational optimal solution ( 𝑦 1 ∗ , … , 𝑦 𝑘 ∗ ) to Mono-LP-Rel whose supports ℒ 1 , … , ℒ 𝑘 are chains in polynomial time via the ellipsoid method [5] (see Appendix A for details). Then, we define 𝑈 𝑖 𝑗 for each 𝑖 ∈ [ 𝑘 ] and 𝑗 ∈ [ 𝑀 ] , and 𝑎 𝑖 𝑗 for each 𝑖 ∈ [ 𝑘 ] and 𝑗 ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] as in the proof of Theorem 1.1. If we can compute

𝑗 ∗ := argmin 𝑗 ∈ [ 2 ​ 𝑚 ​ ( 𝑘 − 1 ) ] ​ ∑ 𝑖 ∈ [ 𝑘 ] 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑎 𝑖 𝑗 ) ,

then any partition 𝑈 1 , … , 𝑈 𝑘 of 𝑁 such that 𝑈 𝑖 ⊆ 𝑈 𝑖 𝑎 𝑖 𝑗 ∗ for every 𝑖 ∈ [ 𝑘 ] satisfies

∑ 𝑖 ∈ [ 𝑘 ] 𝑓 𝑖 ​ ( 𝑈 𝑖 ) ≤ 𝑘 2 ⋅ ∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ∗ ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 ) ≤ 𝑘 2 ⋅ min ⁡ { ∑ 𝑖

1 𝑘 𝑓 𝑖 ​ ( 𝑋 𝑖 ) | 𝑋 1 , … , 𝑋 𝑘 ​ is ​ a ​ partition ​ of ​ 𝑁 } ,

as desired. Hence, it suffices to show that 𝑗 ∗ can be computed in polynomial time. To find 𝑗 ∗ , we set 𝑗 1 := 1 . Then, for 𝑞

2 , 3 , … , we define 𝑗 𝑞 as the minimum integer such that 𝑗 𝑞 > 𝑗 𝑞 − 1 and there exists 𝑖 ∈ [ 𝑘 ] with 𝑈 𝑖 𝑎 𝑖 𝑗 𝑞 ≠ 𝑈 𝑖 𝑎 𝑖 𝑗 𝑞 − 1 . Recall that 𝑛 := | 𝑁 | . Since for each 𝑖 ∈ [ 𝑘 ] , we have 𝑈 𝑖 1 ⊇ 𝑈 𝑖 2 ⊇ ⋯ ⊇ 𝑈 𝑖 𝑀 and there are at most | ℒ 𝑖 | ≤ 𝑛 distinct sets among { 𝑈 𝑖 𝑗 } 𝑗

1 𝑀 , we only need to define 𝑗 𝑞 for 𝑞

1 , 2 , … , 𝑄 with 𝑄 ≤ 𝑘 ​ 𝑛 . Since we have

𝑗 ∗

argmin 𝑗 ∈ { 𝑗 1 , 𝑗 2 , … , 𝑗 𝑄 } ​ ∑ 𝑖 ∈ [ 𝑘 ] 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑎 𝑖 𝑗 ) ,

we can find 𝑗 ∗ by computing the values of ∑ 𝑖 ∈ [ 𝑘 ] 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑎 𝑖 𝑗 𝑞 ) for all 𝑞 ∈ [ 𝑄 ] . By the definition of 𝑈 𝑖 𝑗 and 𝑎 𝑖 𝑗 , we can compute 𝑗 𝑞 in polynomial time for each fixed 𝑞 . Hence, since 𝑄 ≤ 𝑘 ​ 𝑛 , we can compute 𝑗 𝑞 and ∑ 𝑖 ∈ [ 𝑘 ] 𝑓 𝑖 ​ ( 𝑈 𝑖 𝑎 𝑖 𝑗 𝑞 ) for all 𝑞 ∈ [ 𝑄 ] in polynomial time. ∎

3Lower bound on the integrality gap

In this section, we show that the integrality gap of Mono-LP-Rel is at least 𝑘 2 − 𝑘 ​ ( 𝑘 − 1 ) log ⁡ 𝑛 when log ⁡ 𝑛 ≥ 𝑘 . To this end, we explicitly construct monotone submodular functions 𝑓 1 , … , 𝑓 𝑘 such that the integrality gap of Mono-LP-Rel is at least 𝑘 2 − 𝑘 ​ ( 𝑘 − 1 ) log ⁡ 𝑛 .

Suppose that log ⁡ 𝑛 ≥ 𝑘 . Let 𝑝 be the unique positive integer such that 𝑝 ​ 𝑘 ≤ ⌊ log ⁡ 𝑛 ⌋ ≤ ( 𝑝 + 1 ) ​ 𝑘 − 1 . We define

𝒱 := { 𝑣 ∈ ℤ + 𝑘 | ∑ 𝑖

1 𝑘 𝑣 𝑖

𝑝 ​ 𝑘 − 𝑘 + 1 } .

By stars and bars (see e.g., [17, Chapter 1]), we have

| 𝒱 |

( 𝑝 ​ 𝑘 𝑘 − 1 ) ≤ 2 𝑝 ​ 𝑘 ≤ 2 ⌊ log ⁡ 𝑛 ⌋ ≤ 𝑛

| 𝑁 | .

Choose 𝑒 𝑣 ∈ 𝑁 for each 𝑣 ∈ 𝒱 so that all 𝑒 𝑣 are distinct. For each 𝑖 ∈ [ 𝑘 ] , let

𝑁 𝑖 := { 𝑒 𝑣 ∈ 𝑁 ∣ 𝑣 ∈ 𝒱 , 𝑣 𝑖 ≥ 1 } ,

𝑍 𝑖 := { 𝑒 𝑣 ∈ 𝑁 ∣ 𝑣 ∈ 𝒱 , 𝑣 𝑖

0 } .

For each 𝑖 ∈ [ 𝑘 ] , define 𝑓 𝑖 : 2 𝑁 → ℝ as follows: for all 𝑆 ⊆ 𝑁 ,

𝑓 𝑖 ​ ( 𝑆 ) := { max ⁡ { 0 , max ⁡ { 2 ​ 𝑝 + 1 − 𝑣 𝑖 ∣ 𝑒 𝑣 ∈ 𝑆 ∩ 𝑁 𝑖 } }
if ​ 𝑆 ∩ 𝑁 𝑖 ≠ ∅ ​ and ​ 𝑆 ∩ 𝑍 𝑖

∅ ,

0
if ​ 𝑆 ∩ 𝑁 𝑖

∅ ​ and ​ 𝑆 ∩ 𝑍 𝑖

∅ ,

2 ​ 𝑝 ​ 𝑘 + 1

if ​ 𝑆 ∩ 𝑍 𝑖 ≠ ∅ .

Lemma 3.1.

𝑓 𝑖 is monotone submodular for each 𝑖 ∈ [ 𝑘 ] .

Proof.

We first show monotonicity of 𝑓 𝑖 . Take any 𝑆 , 𝑇 ⊆ 𝑁 with 𝑆 ⊆ 𝑇 . If 𝑆 ∩ 𝑁 𝑖

𝑆 ∩ 𝑍 𝑖

∅ , then we have 𝑓 𝑖 ​ ( 𝑆 )

0 ≤ 𝑓 𝑖 ​ ( 𝑇 ) . If 𝑆 ∩ 𝑍 𝑖 ≠ ∅ , then we have 𝑇 ∩ 𝑍 𝑖 ≠ ∅ , which implies 𝑓 𝑖 ​ ( 𝑆 )

𝑓 𝑖 ​ ( 𝑇 )

2 ​ 𝑝 ​ 𝑘 + 1 . Consider the case when 𝑆 ∩ 𝑁 𝑖 ≠ ∅ and 𝑆 ∩ 𝑍 𝑖

∅ . If 𝑇 ∩ 𝑍 𝑖 ≠ ∅ , then we have

𝑓 𝑖 ​ ( 𝑆 )

max ⁡ { 0 , max ⁡ { 2 ​ 𝑝 + 1 − 𝑣 𝑖 ∣ 𝑒 𝑣 ∈ 𝑆 ∩ 𝑁 𝑖 } } ≤ 2 ​ 𝑝 + 1 − 1

2 ​ 𝑝 ≤ 2 ​ 𝑝 ​ 𝑘 + 1

𝑓 𝑖 ​ ( 𝑇 ) .

If 𝑇 ∩ 𝑍 𝑖

∅ , then since 𝑇 ∩ 𝑁 𝑖 ≠ ∅ follows from 𝑆 ∩ 𝑁 𝑖 ≠ ∅ , we have

𝑓 𝑖 ​ ( 𝑆 )

max ⁡ { 0 , max ⁡ { 2 ​ 𝑝 + 1 − 𝑣 𝑖 ∣ 𝑒 𝑣 ∈ 𝑆 ∩ 𝑁 𝑖 } }

≤ max ⁡ { 0 , max ⁡ { 2 ​ 𝑝 + 1 − 𝑣 𝑖 ∣ 𝑒 𝑣 ∈ 𝑇 ∩ 𝑁 𝑖 } }

𝑓 𝑖 ​ ( 𝑇 ) .

Therefore, 𝑓 𝑖 is monotone.

We next show that 𝑓 𝑖 is submodular. Take any 𝑆 , 𝑇 ⊆ 𝑁 . If 𝑆 ∩ 𝑍 𝑖 ≠ ∅ , then by the monotonicity of 𝑓 𝑖 , we have

𝑓 𝑖 ​ ( 𝑆 ) + 𝑓 𝑖 ​ ( 𝑇 )

2 ​ 𝑝 ​ 𝑘 + 1 + 𝑓 𝑖 ​ ( 𝑇 ) ≥ 2 ​ 𝑝 ​ 𝑘 + 1 + 𝑓 𝑖 ​ ( 𝑆 ∩ 𝑇 ) ≥ 𝑓 𝑖 ​ ( 𝑆 ∪ 𝑇 ) + 𝑓 𝑖 ​ ( 𝑆 ∩ 𝑇 ) .

The last inequality follows since 𝑓 𝑖 ​ ( 𝑋 ) ≤ 2 ​ 𝑝 ​ 𝑘 + 1 holds for every 𝑋 ⊆ 𝑁 by the definition of 𝑓 𝑖 . If 𝑆 ∩ 𝑁 𝑖

𝑆 ∩ 𝑍 𝑖

∅ , then since ( 𝑆 ∪ 𝑇 ) ∩ 𝑁 𝑖

𝑇 ∩ 𝑁 𝑖 and ( 𝑆 ∪ 𝑇 ) ∩ 𝑍 𝑖

𝑇 ∩ 𝑍 𝑖 , we have 𝑓 𝑖 ​ ( 𝑆 ∪ 𝑇 )

𝑓 𝑖 ​ ( 𝑇 ) by the definition of 𝑓 𝑖 . This implies that

𝑓 𝑖 ​ ( 𝑆 ) + 𝑓 𝑖 ​ ( 𝑇 )

𝑓 𝑖 ​ ( 𝑆 ) + 𝑓 𝑖 ​ ( 𝑆 ∪ 𝑇 ) ≥ 𝑓 𝑖 ​ ( 𝑆 ∪ 𝑇 ) + 𝑓 𝑖 ​ ( 𝑆 ∩ 𝑇 ) .

The last inequality follows from the monotonicity of 𝑓 𝑖 . Hence, by the symmetry between 𝑆 and 𝑇 , the remaining case is when 𝑆 ∩ 𝑁 𝑖 ≠ ∅ and 𝑆 ∩ 𝑍 𝑖

∅ , and 𝑇 ∩ 𝑁 𝑖 ≠ ∅ and 𝑇 ∩ 𝑍 𝑖

∅ . In this case, we have ( 𝑆 ∪ 𝑇 ) ∩ 𝑁 𝑖 ≠ ∅ and ( 𝑆 ∪ 𝑇 ) ∩ 𝑍 𝑖

∅ , which implies that

𝑓 𝑖 ​ ( 𝑆 ∪ 𝑇 )

max ⁡ { 0 , max ⁡ { 2 ​ 𝑝 + 1 − 𝑣 𝑖 ∣ 𝑒 𝑣 ∈ ( 𝑆 ∪ 𝑇 ) ∩ 𝑁 𝑖 } } .

Take 𝑒 𝑣 ∗ ∈ argmax ​ { 2 ​ 𝑝 + 1 − 𝑣 𝑖 ∣ 𝑒 𝑣 ∈ ( 𝑆 ∪ 𝑇 ) ∩ 𝑁 𝑖 } with the corresponding vector 𝑣 ∗ ∈ 𝒱 . Then, we have 𝑒 𝑣 ∗ ∈ 𝑆 ∩ 𝑁 𝑖 or 𝑒 𝑣 ∗ ∈ 𝑇 ∩ 𝑁 𝑖 . We may assume without loss of generality that 𝑒 𝑣 ∗ ∈ 𝑆 ∩ 𝑁 𝑖 . Then, we have 𝑒 𝑣 ∗ ∈ argmax ​ { 2 ​ 𝑝 + 1 − 𝑣 𝑖 ∣ 𝑒 𝑣 ∈ 𝑆 ∩ 𝑁 𝑖 } . Hence, we have

𝑓 𝑖 ​ ( 𝑆 ) + 𝑓 𝑖 ​ ( 𝑇 )

max ⁡ { 0 , 2 ​ 𝑝 + 1 − 𝑣 𝑖 ∗ } + 𝑓 𝑖 ​ ( 𝑇 )

𝑓 𝑖 ​ ( 𝑆 ∪ 𝑇 ) + 𝑓 𝑖 ​ ( 𝑇 )

≥ 𝑓 𝑖 ​ ( 𝑆 ∪ 𝑇 ) + 𝑓 𝑖 ​ ( 𝑆 ∩ 𝑇 ) .

The last inequality follows from the monotonicity of 𝑓 𝑖 . Therefore, 𝑓 𝑖 is submodular. ∎

We now show that for the monotone submodular functions 𝑓 1 , … , 𝑓 𝑘 defined above, any optimal solution ( 𝑦 1 ∗ , … , 𝑦 𝑘 ∗ ) to Mono-LP-Rel satisfies

( 𝑘 2 − 𝑘 ​ ( 𝑘 − 1 ) log ⁡ 𝑛 ) ⋅ ∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ∗ ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 )

≤ min ⁡ { ∑ 𝑖

1 𝑘 𝑓 𝑖 ​ ( 𝑋 𝑖 ) | 𝑋 1 , … , 𝑋 𝑘 ​ is ​ a ​ partition ​ of ​ 𝑁 } .

(3.1)

The inequality (3) implies that the integrality gap of Mono-LP-Rel is at least 𝑘 2 − 𝑘 ​ ( 𝑘 − 1 ) log ⁡ 𝑛 , which completes the proof of Theorem 1.3.

To prove (3), we first give an upper bound on the value ∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ∗ ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 ) . To this end, we construct a feasible solution to Mono-LP-Rel. For each 𝑖 ∈ [ 𝑘 ] and 𝑗 ∈ [ 𝑝 ​ 𝑘 − 𝑘 + 1 ] , let 𝑁 𝑖 𝑗 := { 𝑒 𝑣 ∈ 𝑁 ∣ 𝑣 ∈ 𝒱 , 𝑣 𝑖 ≥ 𝑗 } . Note that 𝑁 𝑖 1

𝑁 𝑖 . In what follows, we will use 𝑁 𝑖 1 instead of 𝑁 𝑖 for convenience. Let 𝑁 𝑐 := 𝑁 ∖ { 𝑒 𝑣 ∈ 𝑁 ∣ 𝑣 ∈ 𝒱 } . For each 𝑖 ∈ [ 𝑘 ] , define 𝑧 𝑖 ∈ ℝ + 2 𝑁 as follows: for all 𝑆 ⊆ 𝑁 ,

𝑧 𝑖 ​ ( 𝑆 ) := { 1 𝑝 ​ 𝑘 − 𝑘 + 1
if ​ 𝑖

1 ​ and ​ 𝑆

𝑁 1 𝑗 ∪ 𝑁 𝑐 ​ for ​ some ​ 𝑗 ∈ [ 𝑝 ​ 𝑘 − 𝑘 + 1 ] ,

1 𝑝 ​ 𝑘 − 𝑘 + 1
if ​ 2 ≤ 𝑖 ≤ 𝑘 ​ and ​ 𝑆

𝑁 𝑖 𝑗 ​ for ​ some ​ 𝑗 ∈ [ 𝑝 ​ 𝑘 − 𝑘 + 1 ] ,

0

otherwise .

Lemma 3.2.

( 𝑧 1 , … , 𝑧 𝑘 ) is a feasible solution to Mono-LP-Rel.

Proof.

To show the feasibility of ( 𝑧 1 , … , 𝑧 𝑘 ) , we show that

∑ 𝑆 ⊆ 𝑁 , 𝑒 ∈ 𝑆

𝑖 ∈ [ 𝑘 ] 𝑧 𝑖 ​ ( 𝑆 )

1

(3.2)

for every 𝑒 ∈ 𝑁 . For any 𝑒 ∈ 𝑁 𝑐 , we have

∑ 𝑆 ⊆ 𝑁 , 𝑒 ∈ 𝑆

𝑖 ∈ [ 𝑘 ] 𝑧 𝑖 ​ ( 𝑆 )

∑ 𝑗 ∈ [ 𝑝 ​ 𝑘 − 𝑘 + 1 ] 𝑧 1 ​ ( 𝑁 1 𝑗 ∪ 𝑁 𝑐 )

∑ 𝑗 ∈ [ 𝑝 ​ 𝑘 − 𝑘 + 1 ] 1 𝑝 ​ 𝑘 − 𝑘 + 1

1 .

Take any 𝑒 ∈ 𝑁 ∖ 𝑁 𝑐 . Since 𝑒

𝑒 𝑣 for some 𝑣 ∈ 𝒱 , we have

∑ 𝑆 ⊆ 𝑁 , 𝑒 ∈ 𝑆

𝑖 ∈ [ 𝑘 ] 𝑧 𝑖 ​ ( 𝑆 )

∑ 𝑗 ∈ [ 𝑝 ​ 𝑘 − 𝑘 + 1 ]

𝑣 1 ≥ 𝑗 𝑧 1 ​ ( 𝑁 1 𝑗 ∪ 𝑁 𝑐 ) + ∑ 𝑗 ∈ [ 𝑝 ​ 𝑘 − 𝑘 + 1 ]

2 ≤ 𝑖 ≤ 𝑘 , 𝑣 𝑖 ≥ 𝑗 𝑧 𝑖 ​ ( 𝑁 𝑖 𝑗 )

∑ 𝑗 ∈ [ 𝑝 ​ 𝑘 − 𝑘 + 1 ]

𝑣 1 ≥ 𝑗 1 𝑝 ​ 𝑘 − 𝑘 + 1 + ∑ 𝑗 ∈ [ 𝑝 ​ 𝑘 − 𝑘 + 1 ]

2 ≤ 𝑖 ≤ 𝑘 , 𝑣 𝑖 ≥ 𝑗 1 𝑝 ​ 𝑘 − 𝑘 + 1

∑ 𝑗 ∈ [ 𝑝 ​ 𝑘 − 𝑘 + 1 ]

𝑖 ∈ [ 𝑘 ] , 𝑣 𝑖 ≥ 𝑗 1 𝑝 ​ 𝑘 − 𝑘 + 1

𝑝 ​ 𝑘 − 𝑘 + 1 𝑝 ​ 𝑘 − 𝑘 + 1

1 .

The second last equality follows since ∑ 𝑖

1 𝑘 𝑣 𝑖

𝑝 ​ 𝑘 − 𝑘 + 1 . Hence, (3.2) holds for every 𝑒 ∈ 𝑁 , which implies that ( 𝑧 1 , … , 𝑧 𝑘 ) is a feasible solution to Mono-LP-Rel. ∎

By Lemma 3.2 and the optimality of 𝑦 1 ∗ , … , 𝑦 𝑘 ∗ , we have

∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ∗ ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 ) ≤ ∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑧 𝑖 ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 )

∑ 𝑗 ∈ [ 𝑝 ​ 𝑘 − 𝑘 + 1 ] 1 𝑝 ​ 𝑘 − 𝑘 + 1 ​ 𝑓 1 ​ ( 𝑁 1 𝑗 ∪ 𝑁 𝑐 ) + ∑ 2 ≤ 𝑖 ≤ 𝑘 , 𝑗 ∈ [ 𝑝 ​ 𝑘 − 𝑘 + 1 ] 1 𝑝 ​ 𝑘 − 𝑘 + 1 ​ 𝑓 𝑖 ​ ( 𝑁 𝑖 𝑗 )

∑ 𝑗 ∈ [ 𝑝 ​ 𝑘 − 𝑘 + 1 ] 1 𝑝 ​ 𝑘 − 𝑘 + 1 ⋅ max ⁡ { 0 , 2 ​ 𝑝 + 1 − 𝑗 } + ∑ 2 ≤ 𝑖 ≤ 𝑘 , 𝑗 ∈ [ 𝑝 ​ 𝑘 − 𝑘 + 1 ] 1 𝑝 ​ 𝑘 − 𝑘 + 1 ⋅ max ⁡ { 0 , 2 ​ 𝑝 + 1 − 𝑗 }

𝑝 ​ 𝑘 ​ ( 2 ​ 𝑝 + 1 ) 𝑝 ​ 𝑘 − 𝑘 + 1 .

(3.3)

To prove (3), we next provide a lower bound on the right hand side of (3).

Lemma 3.3.

Let 𝑋 1 , … , 𝑋 𝑘 be any partition of 𝑁 . Then, we have

∑ 𝑖

1 𝑘 𝑓 𝑖 ​ ( 𝑋 𝑖 ) ≥ 𝑝 ​ 𝑘 + 𝑘 .

Proof.

If 𝑋 𝑗 ∩ 𝑍 𝑗 ≠ ∅ for some 𝑗 ∈ [ 𝑘 ] , then we have

∑ 𝑖

1 𝑘 𝑓 𝑖 ​ ( 𝑋 𝑖 ) ≥ 𝑓 𝑗 ​ ( 𝑋 𝑗 )

2 ​ 𝑝 ​ 𝑘 + 1 ≥ 𝑝 ​ 𝑘 + 𝑘 .

Hence, it suffices to consider the case when 𝑋 𝑖 ∩ 𝑍 𝑖

∅ for every 𝑖 ∈ [ 𝑘 ] . For each 𝑖 ∈ [ 𝑘 ] , define 𝑥 𝑖 ∈ 𝒱 as follows:

𝑥 𝑗 𝑖 := { 𝑝 ​ 𝑘 − 𝑘 + 1
if ​ 𝑗

𝑖 ,

0

if ​ 𝑗 ∈ [ 𝑘 ] ​ and ​ 𝑗 ≠ 𝑖 .

Then, since 𝑋 𝑖 ∩ 𝑍 𝑖

∅ for each 𝑖 ∈ [ 𝑘 ] , we have 𝑒 𝑥 𝑖 ∈ 𝑋 𝑖 for every 𝑖 ∈ [ 𝑘 ] . Hence, we have 𝑋 𝑖 ∩ 𝑁 𝑖 ≠ ∅ for every 𝑖 ∈ [ 𝑘 ] . For each 𝑖 ∈ [ 𝑘 ] , we define 𝑏 𝑖 := min ⁡ { 𝑣 𝑖 ∣ 𝑒 𝑣 ∈ 𝑋 𝑖 ∩ 𝑁 𝑖 } . We now show that ∑ 𝑖

1 𝑘 𝑏 𝑖 ≤ 𝑝 ​ 𝑘 . Suppose to the contrary that ∑ 𝑖

1 𝑘 𝑏 𝑖 ≥ 𝑝 ​ 𝑘 + 1 . Then, since ∑ 𝑖

1 𝑘 ( 𝑏 𝑖 − 1 ) ≥ 𝑝 ​ 𝑘 − 𝑘 + 1 , there exists 𝑣 ∈ 𝒱 such that 𝑣 𝑖 ≤ 𝑏 𝑖 − 1 for every 𝑖 ∈ [ 𝑘 ] . Choose 𝑖 ∈ [ 𝑘 ] such that 𝑒 𝑣 ∈ 𝑋 𝑖 . Since 𝑋 𝑖 ∩ 𝑍 𝑖

∅ by the assumption, we have 𝑒 𝑣 ∈ 𝑋 𝑖 ∩ 𝑁 𝑖 , which contradicts the definition of 𝑏 𝑖 . Hence, we have ∑ 𝑖

1 𝑘 𝑏 𝑖 ≤ 𝑝 ​ 𝑘 . Therefore, since 𝑋 𝑖 ∩ 𝑁 𝑖 ≠ ∅ and 𝑋 𝑖 ∩ 𝑍 𝑖

∅ for each 𝑖 ∈ [ 𝑘 ] , we have

∑ 𝑖

1 𝑘 𝑓 𝑖 ​ ( 𝑋 𝑖 )

∑ 𝑖

1 𝑘 max ⁡ { 0 , max ⁡ { 2 ​ 𝑝 + 1 − 𝑣 𝑖 ∣ 𝑒 𝑣 ∈ 𝑋 𝑖 ∩ 𝑁 𝑖 } }

≥ ∑ 𝑖

1 𝑘 max ⁡ { 2 ​ 𝑝 + 1 − 𝑣 𝑖 ∣ 𝑒 𝑣 ∈ 𝑋 𝑖 ∩ 𝑁 𝑖 }

2 ​ 𝑝 ​ 𝑘 + 𝑘 − ∑ 𝑖

1 𝑘 min ⁡ { 𝑣 𝑖 ∣ 𝑒 𝑣 ∈ 𝑋 𝑖 ∩ 𝑁 𝑖 }

2 ​ 𝑝 ​ 𝑘 + 𝑘 − ∑ 𝑖

1 𝑘 𝑏 𝑖 ≥ 2 ​ 𝑝 ​ 𝑘 + 𝑘 − 𝑝 ​ 𝑘

𝑝 ​ 𝑘 + 𝑘 .

∎

By Lemma 3.3, we have

min ⁡ { ∑ 𝑖

1 𝑘 𝑓 𝑖 ​ ( 𝑋 𝑖 ) | 𝑋 1 , … , 𝑋 𝑘 ​ is ​ a ​ partition ​ of ​ 𝑁 }

≥ 𝑝 ​ 𝑘 + 𝑘

2 ​ 𝑘 ​ ( 𝑝 + 1 ) 2 ​ ( 𝑝 ​ 𝑘 − 𝑘 + 1 ) 2 ​ ( 𝑝 + 1 ) ​ ( 𝑝 ​ 𝑘 − 𝑘 + 1 )

2 ​ 𝑘 ​ ( 𝑝 + 1 ) ​ ( 𝑝 2 ​ 𝑘 − 𝑘 + 𝑝 + 1 ) 2 ​ ( 𝑝 + 1 ) ​ ( 𝑝 ​ 𝑘 − 𝑘 + 1 )

2 ​ 𝑘 ​ ( 𝑝 + 1 ) ​ ( 𝑝 2 ​ 𝑘 + ( 𝑝 − 1 ) ​ ( 𝑘 − 1 ) − 𝑝 ​ 𝑘 + 2 ​ 𝑝 ) 2 ​ ( 𝑝 + 1 ) ​ ( 𝑝 ​ 𝑘 − 𝑘 + 1 )

≥ 2 ​ 𝑘 ​ ( 𝑝 + 1 ) ​ ( 𝑝 2 ​ 𝑘 − 𝑝 ​ 𝑘 + 2 ​ 𝑝 ) 2 ​ ( 𝑝 + 1 ) ​ ( 𝑝 ​ 𝑘 − 𝑘 + 1 )

𝑝 ​ 𝑘 ​ ( 2 ​ 𝑝 + 2 ) ​ ( 𝑝 ​ 𝑘 − 𝑘 + 2 ) 2 ​ ( 𝑝 + 1 ) ​ ( 𝑝 ​ 𝑘 − 𝑘 + 1 )

≥ 𝑝 ​ 𝑘 ​ ( 2 ​ 𝑝 + 1 ) ​ ( 𝑝 ​ 𝑘 − 𝑘 + 2 ) 2 ​ ( 𝑝 + 1 ) ​ ( 𝑝 ​ 𝑘 − 𝑘 + 1 )

𝑝 ​ 𝑘 ​ ( 2 ​ 𝑝 + 1 ) 𝑝 ​ 𝑘 − 𝑘 + 1 ⋅ ( 𝑘 2 − 𝑘 ​ ( 𝑘 − 1 ) 𝑘 ​ ( 𝑝 + 1 ) )

≥ 𝑝 ​ 𝑘 ​ ( 2 ​ 𝑝 + 1 ) 𝑝 ​ 𝑘 − 𝑘 + 1 ⋅ ( 𝑘 2 − 𝑘 ​ ( 𝑘 − 1 ) log ⁡ 𝑛 ) .

(3.4)

The last inequality follows from the definition of 𝑝 . Combining (3) and (3), we have

( 𝑘 2 − 𝑘 ​ ( 𝑘 − 1 ) log ⁡ 𝑛 ) ⋅ ∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ∗ ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 ) ≤ ( 𝑘 2 − 𝑘 ​ ( 𝑘 − 1 ) log ⁡ 𝑛 ) ⋅ 𝑝 ​ 𝑘 ​ ( 2 ​ 𝑝 + 1 ) 𝑝 ​ 𝑘 − 𝑘 + 1

≤ min ⁡ { ∑ 𝑖

1 𝑘 𝑓 𝑖 ​ ( 𝑋 𝑖 ) | 𝑋 1 , … , 𝑋 𝑘 ​ is ​ a ​ partition ​ of ​ 𝑁 } .

Thus, the inequality (3) holds, which completes the proof of Theorem 1.3.

Acknowledgements

This work was supported by JST ERATO Grant Number JPMJER2301, Japan.

References [1] F. Abbasi, M. Adamczyk, M. Bosch-Calvo, J. Byrka, F. Grandoni, K. Sornat, and A. Tinguely.An 𝑂 ​ ( log ⁡ log ⁡ 𝑛 ) -approximation for submodular facility location.In The 51st International Colloquium on Automata, Languages, and Programming (ICALP), pages 5:1–5:20, 2024. [2] K. Bérczi, K. Chandrasekaran, T. Király, and D. P. Szabo.Approximating submodular matroid-constrained partitioning.arXiv preprint arXiv:2506.19507, 2025. [3] R. Bi, K. Chandrasekaran, and S. Joshi.Monotone submodular multiway partition.In The 26th Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 72–85, 2025. [4] K. Chandrasekaran and C. Chekuri.Min–max partitioning of hypergraphs and symmetric submodular functions.Combinatorica, 43:455–477, 2023. [5] C. Chekuri and A. Ene.Submodular cost allocation problem and applications.In The 38th International Colloquium on Automata, Languages and Programming (ICALP), pages 354–366, 2011. [6] C. Chekuri and A. Ene.Submodular cost allocation problem and applications.arXiv preprint arXiv:1105.2040, 2011. [7] S. Deng, J. Li, and Y. Rabani.Generalized unrelated machine scheduling problem.In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2898–2916, 2023. [8] A. Ene and J. Vondrák.Hardness of submodular cost allocation: Lattice matching and a simplex coloring conjecture.In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014), pages 144–159, 2014. [9] S. R. Etesami.Maximizing social welfare subject to network externalities: A unifying submodular optimization approach.IEEE Transactions on Network Science and Engineering, 11(5):4860–4874, 2024. [10] U. Feige.A threshold of ln ⁡ 𝑛 for approximating set cover.Journal of the ACM, 45(4):634–652, 1998. [11] T. Hirayama, Y. Liu, K. Makino, K. Shi, and C. Xu.A polynomial time algorithm for finding a minimum 4-partition of a submodular function.Mathematical Programming, 207(1–2):717–732, 2023. [12] L. C. Lau, R. Ravi, and M. Singh.Iterative Methods in Combinatorial Optimization.Cambridge University Press, New York, 2011. [13] A. Linhares, N. Olver, C. Swamy, and R. Zenklusen.Approximate multi-matroid intersection via iterative refinement.Mathematical Programming, 183(1–2):397–418, 2020. [14] R. Santiago.New approximations and hardness results for submodular partitioning problems.In 32nd International Workshop on Combinatorial Algorithms (IWOCA), pages 516–530, 2021. [15] R. Santiago and F. B. Shepherd.Multi-agent submodular optimization.In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), pages 23:1–23:10, 2018. [16] A. Schrijver.Combinatorial Optimization: Polyhedra and Efficiency.Springer, Heidelberg, 2003. [17] R. P. Stanley.Enumerative Combinatorics: Volume 1.Cambridge University Press, New York, 2011. [18] Z. Svitkina and É. Tardos.Facility location with hierarchical facility costs.ACM Transactions on Algorithms, 6(2):1–22, 2010. Appendix AConvex program based on the Lovász extension

In this section, we show that LP-Rel is equivalent to the convex program relaxation of MSCA introduced by Chekuri and Ene [5]. Let 𝑁 := { 1 , … , 𝑛 } . Let 𝑓 𝑖 : 2 𝑁 → ℝ be a submodular function with 𝑓 𝑖 ​ ( ∅ )

0 for each 𝑖 ∈ [ 𝑘 ] . Recall that LP-Rel is defined as follows:

( LP-Rel ) minimize
∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 )

subject ​ to
𝑦 𝑖 ∈ ℝ + 2 𝑁 ​ for ​ every ​ 𝑖 ∈ [ 𝑘 ] ,

∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ​ ( 𝑆 ) ​ 𝜒 𝑆

𝟏 .

For a set function 𝑓 : 2 𝑁 → ℝ with 𝑓 ​ ( ∅ )

0 , the Lovász extension 𝑓 ^ : [ 0 , 1 ] 𝑛 → ℝ of 𝑓 is defined as follows: Take any 𝑥 ∈ [ 0 , 1 ] 𝑛 . Relabel the elements in 𝑁 so that 𝑥 1 ≥ 𝑥 2 ≥ ⋯ ≥ 𝑥 𝑛 . For convenience, let 𝑥 𝑛 + 1 := 0 . Let 𝑆 𝑖 := { 1 , 2 , … , 𝑖 } for each 𝑖 ∈ [ 𝑛 ] . The value of 𝑓 ^ ​ ( 𝑥 ) is defined as follows:

𝑓 ^ ​ ( 𝑥 ) := ∑ 𝑖

1 𝑛 ( 𝑥 𝑖 − 𝑥 𝑖 + 1 ) ​ 𝑓 ​ ( 𝑆 𝑖 ) .

Chekuri and Ene [5] introduced the following convex program relaxation of MSCA based on the Lovász extension:

( LE-Rel ) minimize
∑ 𝑖

1 𝑘 𝑓 ^ 𝑖 ​ ( 𝑥 𝑖 )

subject ​ to
𝑥 𝑖 ∈ [ 0 , 1 ] 𝑛 ​ for ​ every ​ 𝑖 ∈ [ 𝑘 ] ,

∑ 𝑖

1 𝑘 𝑥 𝑗 𝑖

1 ​ for ​ every ​ 𝑗 ∈ [ 𝑛 ] .

We now show that any feasible solution ( 𝑥 1 , … , 𝑥 𝑘 ) to LE-Rel can be translated into a feasible solution ( 𝑦 1 , … , 𝑦 𝑘 ) to LP-Rel that has the same objective value and whose supports are chains. Take any feasible solution ( 𝑥 1 , … , 𝑥 𝑘 ) to LE-Rel. We will describe a translation from 𝑥 𝑖 to 𝑦 𝑖 for each 𝑖 ∈ [ 𝑘 ] . We first relabel the elements in 𝑁 so that 𝑥 1 𝑖 ≥ 𝑥 2 𝑖 ≥ ⋯ ≥ 𝑥 𝑛 𝑖 . Let 𝑥 𝑛 + 1 𝑖 := 0 and 𝑆 𝑗 := { 1 , 2 , … , 𝑗 } for each 𝑗 ∈ [ 𝑛 ] . Then, for all 𝑆 ⊆ 𝑁 define 𝑦 𝑖 ​ ( 𝑆 ) as follows:

𝑦 𝑖 ​ ( 𝑆 ) := { 𝑥 𝑗 𝑖 − 𝑥 𝑗 + 1 𝑖
if ​ 𝑆

𝑆 𝑗 ​ and ​ 𝑥 𝑗 𝑖 − 𝑥 𝑗 + 1 𝑖

0 ​ for ​ some ​ 𝑗 ∈ [ 𝑛 ] ,

0

otherwise .

Then, ( 𝑦 1 , … , 𝑦 𝑘 ) is a feasible solution to LP-Rel because for each 𝑖 ∈ [ 𝑘 ] we have

∑ 𝑆 ⊆ 𝑁 𝑦 𝑖 ​ ( 𝑆 ) ​ 𝜒 𝑆

∑ 𝑗 ∈ [ 𝑛 ] ( 𝑥 𝑗 𝑖 − 𝑥 𝑗 + 1 𝑖 ) ​ 𝜒 𝑆 𝑗

𝑥 𝑖

and

∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ​ ( 𝑆 ) ​ 𝜒 𝑆

∑ 𝑖 ∈ [ 𝑘 ] 𝑥 𝑖

𝟏 .

For each 𝑖 ∈ [ 𝑘 ] , we also have

∑ 𝑆 ⊆ 𝑁 𝑦 𝑖 ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 )

∑ 𝑗 ∈ [ 𝑛 ] ( 𝑥 𝑗 𝑖 − 𝑥 𝑗 + 1 𝑖 ) ​ 𝑓 𝑖 ​ ( 𝑆 𝑗 )

𝑓 𝑖 ^ ​ ( 𝑥 𝑖 ) .

Hence, we obtain

∑ 𝑆 ⊆ 𝑁 , 𝑖 ∈ [ 𝑘 ] 𝑦 𝑖 ​ ( 𝑆 ) ​ 𝑓 𝑖 ​ ( 𝑆 )

∑ 𝑖

1 𝑘 𝑓 𝑖 ^ ​ ( 𝑥 𝑖 ) ,

which implies that ( 𝑦 1 , … , 𝑦 𝑘 ) has the same objective value as ( 𝑥 1 , … , 𝑥 𝑘 ) . Similarly, we can translate any feasible solution to LP-Rel whose supports are chains into a feasible solution to LE-Rel that has the same objective value.

Since LE-Rel can be solved in polynomial time via the ellipsoid method [5], an optimal solution to LP-Rel whose supports are chains can be obtained in polynomial time. Chekuri and Ene [6] provided another equivalent linear programming formulation of MSCA called LE-Rel-Primal. We note that LP-Rel is equivalent to LE-Rel-Primal.

Appendix B 𝑘 -polymatroid intersection

Let 𝑁 be a finite set and 𝑘 ≥ 2 a positive integer. For each 𝑖 ∈ [ 𝑘 ] , let 𝑓 𝑖 : 2 𝑁 → ℝ be a submodular function with 𝑓 𝑖 ​ ( ∅ )

0 . For a set function 𝑓 : 2 𝑁 → ℝ , we define 𝑃 ​ ( 𝑓 ) := { 𝑥 ∈ ℝ 𝑁 ∣ 𝑥 ​ ( 𝑆 ) ≤ 𝑓 ​ ( 𝑆 ) ​ for ​ every ​ 𝑆 ⊆ 𝑁 } , where 𝑥 ​ ( 𝑆 ) := ∑ 𝑒 ∈ 𝑆 𝑥 ​ ( 𝑒 ) for every 𝑆 ⊆ 𝑁 . Let 𝑤 ∈ ℝ + 𝑁 be a weight vector. The weighted 𝑘 -polymatroid intersection problem is defined as follows:

( LP 𝑘 ​ -poly ) maximize

𝑤 ⊤ ​ 𝑥

subject ​ to

𝑥 ∈ 𝑃 ​ ( 𝑓 𝑖 ) ​ for ​ every ​ 𝑖 ∈ [ 𝑘 ] .

The linear program LP 𝑘 ​ -poly corresponds to the weighted polymatroid intersection when 𝑘

2 . When 𝑤

𝟏 , the linear program LP 𝑘 ​ -poly is the dual linear program of LP-Rel. For the case when 𝑓 1 , … , 𝑓 𝑘 are matroid rank functions (i.e., the case of weighted 𝑘 -matroid intersection), the integrality gap of LP 𝑘 ​ -poly is 2 when 𝑘

3 [13], and it equals 𝑘 − 1 for arbitrary 𝑘 in the unweighted case 𝑤

𝟏 [12].

Generated on Sat Nov 1 09:37:33 2025 by LaTeXML