Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint

We study the problem of maximizing a monotone submodular function subject to a matroid constraint, and present for it a deterministic non-oblivious local search algorithm that has an approximation guarantee of $1-1/e-\epsilon$ (for any $\epsilon > 0$ ) and query complexity of $\tilde{O}_{\epsilon}(nr)$, where $n$ is the size of the ground set and $r$ is the rank of the matroid. Our algorithm vastly improves over the previous state-of-the-art 0. 5008-approximation deterministic algorithm, and in fact, shows that there is no separation between the approximation guarantees that can be obtained by deterministic and randomized algorithms for the problem considered. The query complexity of our algorithm can be improved to $\tilde{O}_{\epsilon}(n+\hat{r}\sqrt{{n}})$ using randomization, which is nearly-linear for $r=O(\sqrt{n})$, and is always at least as good as the previous state-of-the-art algorithms.

Authors

• Niv Buchbinder
• Moran Feldman

Keywords

• Computer science
• Approximation algorithms
• Search problems
• Complexity theory
• Submodular Maximization
• Matroid Constraint
• Local Algorithm
• Local Search Algorithm
• Objective Function
• Independent Set
• Time Complexity
• Parametrized
• Line Of Work
• Variety Of Algorithms
• Independent System
• Nonnegative Function
• Approximate Ratio
• Auxiliary Function
• Proof Of The Lemma
• General Constraints
• Fast Search
• Single Query
• Law Of Total Expectation
• deterministic algorithm
• fast algorithm