# Constrained Submodular Maximization via a Non-symmetric Technique

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2016.

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

- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (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)
- [The Power of Subsampling in Submodular Maximization](https://mlsanity.com/paper/2104.02772/) (2021)
- [Deletion Robust Non-Monotone Submodular Maximization over Matroids](https://mlsanity.com/paper/2208.07582/) (2022)
- [Beyond Submodularity: A Unified Framework of Randomized Set Selection with Group Fairness Constraints](https://mlsanity.com/paper/2304.06596/) (2023)
- [Non-monotone Sequential Submodular Maximization](https://mlsanity.com/paper/2308.08641/) (2023)
- [Fairness in Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2312.14299/) (2023)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [Data Summarization beyond Monotonicity: Non-monotone Two-Stage Submodular Maximization](https://mlsanity.com/paper/2309.05183/) (2023)
- [Dynamic Non-monotone Submodular Maximization](https://mlsanity.com/paper/2311.03685/) (2023)
- [Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity](https://mlsanity.com/paper/2405.12252/) (2024)
- [Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2409.04415/) (2024)
- [Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit](https://mlsanity.com/paper/2410.08578/) (2024)
- [Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint](https://mlsanity.com/paper/2511.02254/) (2025)
- [Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering](https://mlsanity.com/paper/2609.15539/) (2026)
- [Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits](https://mlsanity.com/paper/2610.18514/) (2026)

## Abstract (arXiv)

The study of combinatorial optimization problems with a submodular objective has attracted much attention in recent years. Such problems are important in both theory and practice because their objective functions are very general. Obtaining further improvements for many submodular maximization problems boils down to finding better algorithms for optimizing a relaxation of them known as the multilinear extension. In this work we present an algorithm for optimizing the multilinear relaxation whose guarantee improves over the guarantee of the best previous algorithm (which was given by Ene and Nguyen (2016)). Moreover, our algorithm is based on a new technique which is, arguably, simpler and more natural for the problem at hand. In a nutshell, previous algorithms for this problem rely on symmetry properties which are natural only in the absence of a constraint. Our technique avoids the need to resort to such properties, and thus, seems to be a better fit for constrained problems.