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.
翻译:子模块最大化是组合优化的核心主题之一。 它在现实世界中发现了许多应用。 在过去几十年中, 提出了一系列的算法来解决这个问题。 但是, 大多数最先进的算法都是随机的。 在亚模块最大化中的确定式算法和随机化算法之间的近似比率方面, 仍然存在不可忽略的差距 。 在本文中, 我们提出了确定式算法, 其近似比率在非分子亚模块最大化中得到了改善 。 具体地说, 我们提供了一种确定性算法 0. 283- o(1)美元近似值算法, 而先前的最佳确定性算法只达到了1/4美元近似率 。 对于 knapsack 限制, 我们提供了一种确定性算法 1/4美元近似值算法, 而前最好的确定性算法只达到了1/6美元近似率 。