Source-linked AI summary
On Maximizing a Weakly Submodular Function over a Matroid Constraint via the Greedy Algorithm
Justin Ward, Moran Feldman
TL;DR
The paper asks whether standard greedy retains a constant-factor guarantee for general γ-weakly submodular maximization under matroid constraints. It constructs a family of γ-weakly submodular functions and simplified partition matroids, proving that for every γ∈(0,1), greedy's approximation ratio deteriorates with the ground-set size.
Problem
Whether standard greedy has a constant-factor approximation for general γ-weakly submodular functions under matroid constraints remains unresolved beyond cardinality constraints.
Method
The paper constructs a non-negative monotone γ-weakly submodular objective together with a simplified partition matroid and analyzes standard greedy on the resulting instance.
Results
For every γ∈(0,1), greedy's approximation ratio can be as low as O(γ / ((1−γ)^2 log n)) on a rank n−1 simplified partition matroid.
Takeaways & Limitations
Unlike cardinality constraints, general matroid constraints do not yield a constant-factor guarantee for standard greedy on γ-weakly submodular functions without additional restrictions or algorithmic insights.
Takeaways & Limitations
The construction and theorem use a simplified partition matroid, a particular matroid family in which independent sets contain exactly one element from each part.
Abstract
from arXiv · showhide
We consider the problem of approximately maximizing a weakly submodular function using the standard greedy algorithm, which is known to give tight approximation results for such functions under a cardinality constraint. We show that this is not the case for general matroid constraints. For any $γ< 1$, we give a family of $γ$-weakly submodular functions and a simple partition matroid constraint and show that the standard greedy algorithm provides no constant approximation for the resulting constrained maximization problem.
1 Introduction
The introduction reviews greedy guarantees for submodular and weakly submodular maximization, then identifies a gap for general matroid constraints and gives a negative result for standard greedy.
- Submodular functions model diminishing returns and arise in combinatorial optimization, economics, game theory, machine learning, image processing, and decision and control.
- 1−1/e is the greedy approximation ratio for monotone submodular maximization under a cardinality constraint, while the ratio is 1/2 under a general matroid constraint.
- The submodularity ratio γ measures how closely a monotone set function exhibits submodular behavior, with γ=1 for submodular functions.
- 1−e−γ is the greedy approximation guarantee for γ-weakly submodular functions under a cardinality constraint.
- Before this paper, non-trivial guarantees for γ-weakly submodular maximization under constraints beyond cardinality were largely unresolved, despite a constant-factor guarantee for randomized greedy under matroids.
- For every γ∈(0,1), the paper constructs a non-negative monotone γ-weakly submodular function and a simplified partition matroid where greedy achieves only O(γ / ((1−γ)^2 log n)).
2 Preliminaries
The preliminaries define marginal contributions, monotonicity, weak submodularity, matroids, and the simplified partition matroids used by the paper, together with the standard greedy procedure.
- Set Functions: For an element u and set S, f(u | S) is the value increase from adding u; f(T | S) analogously measures the increase from adding a set T.
- Set Functions: A function is monotone when every feasible addition has nonnegative marginal contribution, and it is γ-weakly submodular when its submodularity ratio is at least γ.
- Set Functions: A monotone function is 1-weakly submodular exactly when it is submodular.
- Matroids: A matroid consists of a ground set N and independent subsets I satisfying inclusion, nonempty-set, and augmentation properties.
- Matroids: A simplified partition matroid of rank k partitions N into k parts and requires an independent set to contain exactly one element from each part.
- The Greedy Algorithm: The standard greedy algorithm repeatedly selects the feasible element with the largest marginal increase until no feasible addition remains.
3 Bad Instance
The bad instance pairs a simplified partition matroid with a carefully constructed non-negative, monotone, γ-weakly submodular function so greedy selects a much worse base than the optimum. The resulting approximation ratio decreases as O(γ/((1−γ)^2 log n)).
- Construction: The instance uses ground set N = Z ∪ A, where Z has n−2 elements and A = {o, v}; the partition matroid permits exactly one element from A.Its two bases are Z ∪ {v} and Z ∪ {o}.
- Construction: The objective is built from g(x) = ln(1 + x) and a decreasing sequence a_i = γ · min{g(i) − g(i−1), 2i^−β}, with β = γ + γ^−1 − 1 > 1.The sequence satisfies a_i ≤ γ/i.
- Construction: Sets containing o receive roughly g(|S|), whereas sets without o receive roughly the sum of the a_i terms; this creates a growing value gap while preserving the target function properties.The construction is designed so sets containing o are more valuable than same-size sets without o, with the gap increasing with |S|.
- Function properties: The constructed function is non-negative and monotone, and Lemma 3.4 establishes that it is γ-weakly submodular.The proof handles cases according to whether o appears in the compared sets, using concavity of g and properties of the sequence a_i.
- Greedy failure: Greedy selects v first because f(v | ∅) = 2a_1 exceeds the initial marginal value of every other element, making o infeasible thereafter.Greedy therefore outputs G = Z ∪ {v}, while the alternative base O = Z ∪ {o} is substantially more valuable.
- Greedy failure: The resulting approximation ratio is O(γ/((1−γ)^2 log n)), so for fixed γ < 1 it is not bounded below by a positive constant as n grows.The comparison is expressed through f(G) = Ω((1−γ)^2 log n / γ) relative to the better base.