Source-linked AI summary
Stronger Hardness for Submodular Maximization Subject to a Matroid Constraint
Moran Feldman, Alan Kuhnle
TL;DR
General submodular maximization under matroid constraints has a gap between its algorithmic and hardness bounds, and the hardness result had not improved for 15 years. This paper applies the symmetry-gap framework to prove stronger value-oracle hardness, including for cardinality and simplified partition constraints. It rules out sub-exponential-time algorithms achieving a (8/17+ε)-approximation for non-negative objectives.
Problem
General submodular maximization under matroid constraints had a 0.401-approximation algorithm and an approximately 0.477 hardness bound, with the hardness result unchanged for 15 years.
Source: §1 · pp. 1–2Method
The paper uses the symmetry-gap framework to derive hardness for general matroid constraints and refined constraint classes.
Source: §2.2 · p. 4, §3 · p. 6, §4.1 · p. 8Results
No sub-exponential-time value-oracle algorithm can guarantee a (8/17+ε)-approximation for non-negative submodular maximization, even with cardinality or simplified partition constraints.
Source: §1 · p. 2Takeaways & Limitations
The stronger hardness bound applies even to cardinality and simplified partition matroid constraints.
Source: §1 · p. 2The result assumes a non-negative objective; without non-negativity, no constant multiplicative guarantee is possible.
Source: §1 · p. 2
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies hardness for maximizing general, possibly non-monotone submodular functions under matroid constraints, where prior hardness had remained unchanged for 15 years. It proves a stronger value-oracle hardness bound, including for cardinality and simplified partition constraints.
1 Introduction
- For monotone submodular objectives, the Continuous Greedy algorithm closes the gap at 1 −1/e for general matroid constraints.Earlier, the greedy algorithm guaranteed 1/2 for general matroids and 1 −1/e for cardinality constraints.Source: §1 · p. 1
- General submodular maximization under matroid constraints had a 0.401-approximation algorithm, while the earlier hardness was approximately 0.477.The algorithmic bound is attributed to Buchbinder & Feldman, and the hardness result to Oveis Gharan & Vondrák [13].Source: §1 · p. 1
- The prior 0.477 hardness bound had remained state of the art for 15 years, despite evidence that a large family of instances matched the Measured Continuous Greedy algorithm’s guarantee.The authors use this history to motivate why the new result challenges the apparent tightness of the earlier bound.Source: §1 · pp. 1–2
- No sub-exponential-time value-oracle algorithm can guarantee a (8/17+ε)-approximation, even under cardinality or simplified partition matroid constraints.The theorem assumes a non-negative submodular objective.Source: §1 · p. 2
- The paper also notes that without non-negativity, no constant multiplicative guarantee is possible.The theorem’s non-negativity assumption is standard in the cited prior work.Source: §1 · p. 2
2 Preliminaries
The preliminaries define the submodular maximization problem and its oracle model, then introduce the symmetry-gap framework used to derive hardness for refined constraints. They also establish notation for indicators and characteristic vectors.
2.1 Problem Related Definitions
- A submodular set function has diminishing marginal gains, and its multilinear extension is the expected value of the function on a random set that independently includes each element with probability x_u.The function is non-negative when every set has value at least zero, and monotone when inclusion cannot decrease its value.Source: §2.1 · p. 2
- A matroid constraint specifies feasible independent sets through down-closedness and exchange; partition matroids impose per-part cardinality limits, with uniform matroids giving cardinality constraints.For general matroids, the independence system may be accessed through an independence oracle, while the objective is accessed through a value oracle.Source: §2.1 · pp. 2–3
2.2 Symmetry Gap
- The symmetry-gap framework converts a symmetric instance with gap γ into value-oracle hardness for problems whose constraints are refinements, ruling out (1+ε)γ-approximation with exponentially many required queries.The theorem also applies to monotone objectives when the original objective is monotone.Source: §2.2 · pp. 3–4
2.3 Additional Notation
- The notation 1[C] denotes an indicator for condition C, while 1_S denotes the characteristic vector of set S.These symbols are used in the symmetry definitions and feasible-set representations.Source: §2.3 · p. 4
3 Symmetric Instance
The section constructs a symmetric submodular instance and bounds its symmetry gap, then transfers that bound to hardness for general matroid constraints.
3 Symmetric Instance
- The hard instance uses element families A, B, and C, is parameterized by ℓ, w1, and w2, and has a simplified partition constraint with one part containing all of A.Source: §3 · p. 4
- The objective uses g_X,Y(S), a hyperedge-cut term that is 1 when S intersects X but not all of Y; the resulting f is non-negative and submodular.Source: §3 · p. 4
- A feasible integral set O has value at least ℓ.Source: §3 · p. 5
- Averaging feasible vectors over the permutation group gives common coordinates across A, B, and C, enabling an upper bound on the symmetric objective value.The proof uses the resulting expression and bounds to establish the symmetry-gap guarantee.Source: §3 · pp. 5–6
- For w1 = w2 = 6/17, the instance’s symmetry gap is at most 8/17 + ℓ^-1.These parameter values minimize the symmetry-gap guarantee.Source: §3 · p. 6
- Setting ε′ = ε/3 and ℓ = ceil(3/ε) transfers the refinement hardness to Theorem 1.1, since every refinement of F is a generalized partition matroid.Source: §3 · p. 6
4 Hardness for Special Classes of Matroid Constraints
The section extends symmetry-gap hardness to simplified partition and cardinality constraints. It establishes the claimed hardness for both constraint classes through parallel refinements and a modified cardinality instance.
4.1 Hardness for Simplified Partition Matroid Constraints
- Parallel refinements preserve symmetry and approximate the original fractional optimum, enabling the symmetry-gap hardness argument to apply to simplified partition constraints.For sufficiently large copy sets, a feasible refined set has multilinear-extension value within ε of the original fractional optimum.Source: §4.1 · pp. 7–8
- No sub-exponential time algorithm guarantees a (1+ε′)(8/17+ℓ^-1)-approximation for non-negative submodular maximization under a simplified partition matroid.Parallel refinements preserve the properties needed to transfer the symmetry-gap hardness to this constraint class.Source: §4.1 · p. 8
4.2 Hardness for Cardinality Constraints
- The cardinality construction replaces each a_i with ℓ² copies, defines f′(S)=F(ξ(S)), and preserves non-negativity and submodularity.The copies act as fractions of the original elements, allowing the modified instance to use a cardinality constraint.Source: §4.2 · p. 9
- The cited passage gives a parameter-specific upper bound: in particular, for w1 = w2 = 6/17, the above symmetry gap is at most 8/17+O(ℓ^-1).Source: §4.2 · p. 11
- No sub-exponential time algorithm guarantees a (1+ε′)(8/17+O(ℓ^-1))-approximation on the constructed refinements, which are cardinality constraints.Every refinement of the modified instance is a cardinality constraint.Source: §4.2 · p. 11
A Determining the Parameters w1 and w2
The appendix chooses w1 and w2 to minimize the symmetry-gap guarantee. It first minimizes one argument over w2, then balances the two arguments over α.
A Determining the Parameters w1 and w2
- With α = 1 − w1 − w2/2 ∈ (0, 1), the argument of (3) is minimized at w2 = 2(1 − α)/3 > 0; substituting this valid choice into (3) gives a symmetry gap.Source: A Determining the Parameters w1 and w2 · pp. 11–12
- For fixed α, the second argument is minimized at w2=2(1−α)/3.The derivative’s sign is determined by −1+α+3w2/2.Source: A Determining the Parameters w1 and w2 · pp. 11–12
- Setting the increasing and decreasing arguments equal gives α=8/17 and minimizes their maximum.The balancing equation is α=8(1−α)/9.Source: A Determining the Parameters w1 and w2 · p. 12
AI Usage Disclosure
The authors report that GPT-5.6-Sol found the symmetric instance during automated exploration, while they wrote the paper’s presentation without AI assistance and checked the mathematical arguments.
AI Usage Disclosure
- GPT-5.6-Sol found the symmetric instance during an extended automated exploration run; the authors wrote the presentation without AI assistance and checked all mathematical arguments.The authors state that they take full responsibility for the paper’s content.Source: AI Usage Disclosure · p. 12