Efficient deterministic algorithms for maximizing symmetric submodular functions

Symmetric submodular maximization is an important class of combinatorial optimization problems, including MAX-CUT on graphs and hyper-graphs. The state-of-the-art algorithm for the problem over general constraints has an approximation ratio of 0. 432 [16]. The algorithm applies the canonical continuous greedy technique that involves a sampling process. It, therefore, suffers from high query complexity and is inherently randomized. In this paper, we present several efficient deterministic algorithms for maximizing a symmetric submodular function under various constraints. Specifically, for the cardinality constraint, we design a deterministic algorithm that attains a 0. 432 ratio and uses O ( k n ) queries. Previously, the best deterministic algorithm attains a 0. 385 − ϵ ratio and uses O ( k n ( 10 9 ϵ ) 20 9 ϵ − 1 ) queries [12]. For the matroid constraint, we design a deterministic algorithm that attains a 1 / 3 − ϵ ratio and uses O ( k n log ⁡ ϵ − 1 ) queries. Previously, the best deterministic algorithm can also attain 1 / 3 − ϵ ratio but it uses much larger O ( ϵ − 1 n 4 ) queries [24]. For the packing constraints with a large width, we design a deterministic algorithm that attains a 0. 432 − ϵ ratio and uses O ( n 2 ) queries. To the best of our knowledge, there is no deterministic algorithm for the constraint previously. The last algorithm can be adapted to attain a 0. 432 ratio for single knapsack constraint using O ( n 4 ) queries. Previously, the best deterministic algorithm attains a 0. 316 − ϵ ratio and uses O ˜ ( n 3 ) queries [2].

Authors

• Zongqi Wan Institute of Computing Technology, Chinese Academy of Sciences University of Chinese Academy of Sciences
• Jialin Zhang Nanjing University of Aeronautics and Astronautics
• Xiaoming Sun Institute of Computing Technology, Chinese Academy of Sciences University of Chinese Academy of Sciences
• Zhijie Zhang Fuzhou University

Keywords

• Symmetric submodular maximization
• Deterministic algorithm
• Approximation algorithm