Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions

Abstract

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-\hat{I}\mu$ ratio and uses $O\left(kn(\frac{10}{9\hat{I}\mu }{)}^{\frac{20}{9\hat{I}\mu }-1}\right)$ queries. For the matroid constraint, we design a deterministic algorithm that attains a $1/3-\hat{I}\mu$ ratio and uses $O(kn\log \hat{I}{\mu }^{-1})$ queries. Previously, the best deterministic algorithm can also attain $1/3-\hat{I}\mu$ ratio but it uses much larger $O(\hat{I}{\mu }^{-1}{n}^4)$ queries. For the packing constraints with a large width, we design a deterministic algorithm that attains a $0.432-\hat{I}\mu$ 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-\hat{I}\mu$ ratio and uses $\tilde{O}(n^3)$ queries.