.png){kind=icon}
返回
Fast approximation algorithm for non-monotone DR-submodular maximization under size constraint
.png){kind=icon}
PRE
AI
DOI：10.1007/s10878-025-01374-4.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
本研究探讨了在基数为n的基集上，受限于规模约束k的非单调DR-次模最大化问题。我们提出了两种用于解决该问题的近似算法，分别命名为FastDrSub和FastDrSub+。FastDrSub提供了0.044的近似比，查询复杂度为O(n log(k))。第二种算法FastDrSub+在此基础上进行改进，对于输入参数ε>0，在查询复杂度为O(n log k)的条件下，近似比为1/4 - ε。因此，我们提出的算法是该问题中首次具有常数近似比的低复杂度O(n log(k))算法。此外，两种算法均经过实验评估，并与现有最先进方法进行比较，证明了它们在解决以DR-次模目标函数为特征的收益最大化问题时的有效性。实验结果表明，我们提出的算法在查询复杂度和解质量两方面均显著优于现有方法。
Keyword:
Approximation algorithm
Submodular
DR-submodular
Integer lattice
Size constraint
期刊
J
IF:
1.1
论文数:
80
被引数:
0
机构
暂无机构信息
引用论文
.png){kind=icon}
分享收藏
分享收藏分享收藏
查看更多内容