Improved deterministic algorithms for non-monotone submodular maximization

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.

Authors

• Xiaoming Sun
• Jialin Zhang Institute of Computing Technology, Chinese Academy of Sciences & University of the Chinese Academy of Sciences
• Shuo Zhang Henan Key Laboratory of Quantum Information and Cryptography
• Zhijie Zhang Fuzhou University

Keywords

• Submodular maximization
• Deterministic algorithms
• Derandomization
• Twin greedy
• Multiplicative updates