.png){kind=icon}
返回
Efficient Deterministic Bicriteria Approximation Algorithms for k-Submodular Cover Problem
.png){kind=icon}
PRE
AI
DOI：10.1142/s0217595926500144.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们研究了在大小为n的基集V上的k-次模覆盖（kSC）问题，其目标是为找到k个具有最小成本的互不相交的V的子集，使得一个k-次模效用函数超过给定阈值。该问题推广了著名的次模覆盖（SC）问题，并在人工智能和组合优化中具有广泛应用。然而，现有的kSC近似算法可能无法在多项式时间内运行。在本工作中，我们提出了两种双标准近似算法，这些算法不仅改进了性能保证，而且与当前最优算法相比显著降低了查询复杂度。
Keyword:
Combinatorial optimization
approximation algorithm
k-submodular cover
期刊
A
IF:
1
论文数:
60
被引数:
0
机构
引用论文
暂无论文信息