Stronger limitations found for optimizing under matroid constraints
Stronger Hardness for Submodular Maximization Subject to a Matroid Constraint
Data Structures and Algorithms
Summary
Maximizing submodular functions under matroid constraints is important for many optimization tasks. Current best algorithms can approximate the maximum solution up to about 40%, but it was only known that no algorithm can go beyond about 48%. The authors improve this negative limit slightly to around 47%, even for simpler cases. This means better algorithms than 47% approximation are ruled out under common assumptions.
What this means in practice
- •For optimization engineers: Understand fundamental limits when designing algorithms for resource allocation problems with independence constraints.
- •For machine learning engineers: Know approximation boundaries for submodular maximization tasks in feature selection under constraints.
A theory result. No direct application yet.
Authors
Moran Feldman, Alan Kuhnle
Abstract
Maximizing a submodular function subject to a matroid constraint is a cornerstone problem in combinatorial optimization. The state-of-the-art algorithm for this problem obtains $0.401$-approximation~\cite{buchbinder2024constrained}, and the state-of-the-art hardness result shows that no polynomial time algorithm can obtain better than $0.478$-approximation for this problem~\cite{oveisgharan2011submodular}. In this work, we present the first improvement in $15$ years for the hardness result, showing that no polynomial time algorithm in the value-oracle model can obtain better than $8/17 \approx 0.471$-approximation, even for the special case of a cardinality or (simplified) partition matroid constraint.