In the maximum coverage problem, given a ground set N of elements, a collection \(\mathcal {S}\) of m subsets of N, and an integer k, one needs to select k sets from \(\mathcal {S}\) so that their union has the largest cardinality. The min-k-union problem (MkU) is a minimization counterpart of maximum coverage, which chooses k sets among \(\mathcal {S}\) with the smallest union size. MkU can also be interpreted as an interdiction problem. Given an instance \((N,\mathcal {S}, k)\) and then deriving an integer \(k'= m-k\) , the goal is to remove \(k'\) sets from \(\mathcal S\) so that the remaining sets can cover as few elements as possible. In this paper, two extensions of MkU are investigated. We first consider a general maximum coverage interdiction. For an instance \((N,\mathcal {S}, k_f)\) , we can remove up to \(k_l\) sets from \(\mathcal S\) so that the resulting maximum coverage instance has a least maximum coverage. An \(\widetilde{O}(\sqrt{m})\) -approximation algorithm is derived, while a lower bound of \(\varOmega (m^{1/4})\) under the “Dense versus Random” conjecture for MkU [Chlamtáč et al.’17] applies to our problem as well. The second problem deals with monotone submodular minimization with cardinality constraints. Given a ground set N of n elements, a nonnegative monotone submodular function f on N, and an integer k, we are required to find a size-k set \(S \subseteq N\) that minimizes f(S). We propose a 2 \(\sqrt{n}\) -approximation algorithm, matching (up to a logarithmic factor) the lower bound of \(\varOmega (\sqrt{\frac{n}{\ln n}})\) [Svitkina and Fleischer’11].

On Extensions of Min-k-Union \(^\star \)

会议论文
发表日期：

2025年

查看全文

Hua Chen,
Lin Chen,
Shenghao Ye,
Guochuan Zhang

摘要

In the maximum coverage problem, given a ground set N of elements, a collection \(\mathcal {S}\) of m subsets of N, and an integer k, one needs to select k sets from \(\mathcal {S}\) so that their union has the largest cardinality. The min-k-union problem (MkU) is a minimization counterpart of maximum coverage, which chooses k sets among \(\mathcal {S}\) with the smallest union size. MkU can also be interpreted as an interdiction problem. Given an instance \((N,\mathcal {S}, k)\) and then deriving an integer \(k'= m-k\) , the goal is to remove \(k'\) sets from \(\mathcal S\) so that the remaining sets can cover as few elements as possible. In this paper, two extensions of MkU are investigated. We first consider a general maximum coverage interdiction. For an instance \((N,\mathcal {S}, k_f)\) , we can remove up to \(k_l\) sets from \(\mathcal S\) so that the resulting maximum coverage instance has a least maximum coverage. An \(\widetilde{O}(\sqrt{m})\) -approximation algorithm is derived, while a lower bound of \(\varOmega (m^{1/4})\) under the “Dense versus Random” conjecture for MkU [Chlamtáč et al.’17] applies to our problem as well. The second problem deals with monotone submodular minimization with cardinality constraints. Given a ground set N of n elements, a nonnegative monotone submodular function f on N, and an integer k, we are required to find a size-k set \(S \subseteq N\) that minimizes f(S). We propose a 2 \(\sqrt{n}\) -approximation algorithm, matching (up to a logarithmic factor) the lower bound of \(\varOmega (\sqrt{\frac{n}{\ln n}})\) [Svitkina and Fleischer’11].