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$. 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(kn)$ queries. Previously, the best deterministic algorithm attains a 0.385-ε ratio and uses O(kn (10/9ε)20/9ε-1) queries. For the matroid constraint, we design a deterministic algorithm that attains a 1/3-ε ratio and uses O(knlog ε⁻¹) queries. Previously, the best deterministic algorithm can also attain 1/3-ε ratio but it uses much larger O(ε⁻¹n⁴) queries. For the packing constraints with a large width, we design a deterministic algorithm that attains a 0.432-ε ratio and uses O(n²) 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⁴) queries. Previously, the best deterministic algorithm attains a 0.316-ε ratio and uses O(n³) queries.