Guided Combinatorial Algorithms for Submodular Maximization

For constrained, not necessarily monotone submodular maximization, guiding the measured continuous greedy algorithm with a local search algorithm currently obtains the state-of-the-art approximation factor of 0. 401 buchbinder2023constrained. These algorithms rely upon the multilinear extension and the Lovasz extension of a submodular set function. However, the state-of-the-art approximation factor of combinatorial algorithms has remained 1/e 0. 367 buchbinder2014submodular. In this work, we develop combinatorial analogues of the guided measured continuous greedy algorithm and obtain approximation ratio of 0. 385 in kn queries to the submodular set function for size constraint, and 0. 305 for a general matroid constraint. Further, we derandomize these algorithms, maintaining the same ratio and asymptotic time complexity. Finally, we develop a deterministic, nearly linear time algorithm with ratio 0. 377.