The Ground-Set-Cost Budgeted Maximum Coverage Problem

Irving van Heuven van Staereling

doi:10.1007/s00224-025-10248-5

2025-11-20

Irving van Heuven van Staereling

Bart de Keijzer *

Guido Schäfer

DOI：10.1007/s00224-025-10248-5

原文链接

原文求助

摘要

En 中文

我们研究了预算最大覆盖问题的以下自然变体：给定一个预算B和一个超图G=(V,E)，其中每个顶点具有非负成本和非负利润。目标是从E中选择一组超边T（T是E的子集），使得被T覆盖的顶点的总成本不超过B，并且所有被覆盖顶点的总利润最大化。这是最大覆盖问题的自然推广。我们对该问题的兴趣源于其在赞助搜索拍卖中的竞价优化应用。显然，该问题至少与预算最大覆盖问题（其中成本与所选超边而非被覆盖顶点相关联）一样难。这意味着对于任意ε>0，该问题无法达到(1-1/e+ε)的近似比。此外，标准的贪心方法无法为我们的问题变体提供常数因子近似比。事实上，通过从Densest k-Subgraph问题进行归约，可以证明在指数时间假设下，我们的问题无法达到常数因子近似比。我们的主要结果如下：(i.) 我们为图结构获得了(1-1/√e)/2近似算法。(ii.) 如果超图的关联图是一棵森林（即该超图是Berge-acyclic的），我们推导出一个完全多项式时间近似方案(FPTAS)。我们将这一结果扩展到关联图具有固定大小反馈超边节点集的情况。(iii.) 对于所有ε>0，我们给出了(1-ε)/(2d²)近似算法，其中d是顶点的最大度数。

Keyword:

Maximum coverage problem

Approximation algorithms

Hypergraphs

Submodular optimization