论文标题
改进了非单词酮次管的确定性算法
Improved Deterministic Algorithms for Non-monotone Submodular Maximization
论文作者
论文摘要
supporular最大化是组合优化的核心主题之一。它在现实世界中发现了许多应用。在过去的几十年中，为此问题提出了一系列算法。但是，大多数最新算法都是随机的。相对于确定性和随机算法之间的近似值，在下最大化中仍然存在不可忽略的差距。 在本文中，我们提出了确定性算法，具有提高的非单调性最大化近似值的近似值。具体而言，对于Matroid约束，我们提供了确定性的$ 0.283-O（1）$近似算法，而先前的最佳确定性算法仅达到$ 1/4 $ $近似值。对于背包约束，我们提供确定性的$ 1/4 $近似算法，而以前的最佳确定性算法仅达到$ 1/6 $近似值。对于具有较大宽度的线性包装约束，我们提供确定性的$ 1/6-ε$近似算法。据我们所知，目前尚无确定性近似算法的约束算法。
Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic $0.283-o(1)$ approximation algorithm, while the previous best deterministic algorithm only achieves a $1/4$ approximation ratio. For the knapsack constraint, we provide a deterministic $1/4$ approximation algorithm, while the previous best deterministic algorithm only achieves a $1/6$ approximation ratio. For the linear packing constraints with large widths, we provide a deterministic $1/6-ε$ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints.
