In this work, we consider the Submodular Maximization under Knapsack (SMK)
constraint problem over the ground set of size $n$. The problem recently
attracted a lot of attention due to its applications in various domains of
combination optimization, artificial intelligence, and machine learning. We
improve the approximation factor of the fastest deterministic algorithm from
$6+\epsilon$ to $5+\epsilon$ while keeping the best query complexity of $O(n)$,
where $\epsilon >0$ is a constant parameter. Our technique is based on
optimizing the performance of two components: the threshold greedy subroutine
and the building of two disjoint sets as candidate solutions. Besides, by
carefully analyzing the cost of candidate solutions, we obtain a tighter
approximation factor.

在本研究中，我们考虑了基于背包约束的子模型最大化问题，该问题涉及大小为 n 的总体。我们将最快确定性算法的近似因子从 6+ε 改进为 5+ε，同时保持了 O (n) 的最佳查询复杂度。我们的技术是基于两个组件的性能优化：阈值贪婪子程序和建立两个不相交集合作为候选解。此外，通过仔细分析候选解的成本，我们获得了更紧的近似因子。