# Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2020.

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

- [Dynamic Algorithms for Matroid Submodular Maximization](https://mlsanity.com/paper/2306.00959/) (2023)
- [Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2305.10292/) (2023)
- [Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint](https://mlsanity.com/paper/2405.13994/) (2024)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2409.04415/) (2024)
- [Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint](https://mlsanity.com/paper/2511.02254/) (2025)
- [Matroid Algorithms Under Size-Sensitive Independence Oracles](https://mlsanity.com/paper/2605.00201/) (2026)
- [Fine-Tuning Diffusion Language Models with Context Selection and Target Weighting](https://mlsanity.com/paper/2609.38385/) (2026)

## Abstract (arXiv)

We study the problem of maximizing a non-monotone, non-negative submodular function subject to a matroid constraint. The prior best-known deterministic approximation ratio for this problem is frac14-ε under O((n4/ε)log n) time complexity. We show that this deterministic ratio can be improved to frac14 under O(nr) time complexity, and then present a more practical algorithm dubbed TwinGreedyFast which achieves frac14-ε deterministic ratio in nearly-linear running time of O(fracnεlogfracrε). Our approach is based on a novel algorithmic framework of simultaneously constructing two candidate solution sets through greedy search, which enables us to get improved performance bounds by fully exploiting the properties of independence systems. As a byproduct of this framework, we also show that TwinGreedyFast achieves frac12p+2-ε deterministic ratio under a p-set system constraint with the same time complexity. To showcase the practicality of our approach, we empirically evaluated the performance of TwinGreedyFast on two network applications, and observed that it outperforms the state-of-the-art deterministic and randomized algorithms with efficient implementations for our problem.