May, 2024
非单调子模型最大化在线性查询复杂度下的增强确定性近似算法
Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity
Canh V. Pham
TL;DR在本研究中,我们考虑了基于背包约束的子模型最大化问题,该问题涉及大小为 n 的总体。我们将最快确定性算法的近似因子从 6+ε 改进为 5+ε,同时保持了 O (n) 的最佳查询复杂度。我们的技术是基于两个组件的性能优化:阈值贪婪子程序和建立两个不相交集合作为候选解。此外,通过仔细分析候选解的成本,我们获得了更紧的近似因子。