# Deterministic (1/2 + ε)-Approximation for Submodular Maximization over a Matroid

arXiv: https://arxiv.org/abs/1807.05532 · HTML: https://mlsanity.com/paper/1807.05532/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2018.

## Built on by (most cited first, 1 of 1)

- [A Note On Deterministic Submodular Maximization With Bounded Curvature](https://mlsanity.com/paper/2409.02943/) (2024)

## Abstract (arXiv)

We study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves (1/2 + ε)-approximation for the problem. This algorithm is the first deterministic algorithm known to improve over the 1/2-approximation ratio of the classical greedy algorithm proved by Nemhauser, Wolsely and Fisher in 1978.