Key points are not available for this paper at this time.
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 (109) ^20{9-1}) queries. For the matroid constraint, we design a deterministic algorithm that attains a 1/3- ratio and uses O (kn ^-1) queries. Previously, the best deterministic algorithm can also attain 1/3- ratio but it uses much larger O (^-1n⁴) 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.
Wan et al. (Thu,) studied this question.