Submodular functions capture the intuitive law of diminishing returns: the marginal benefit of adding an item to a selection decreases as the set of already selected items grows. When maximizing these functions without any restrictions, a simple greedy strategy—always picking the item with the highest immediate marginal gain—works remarkably well.
However, real-world applications rarely allow unconstrained selection. Whether allocating marketing budgets, placing sensors, or coordinating ad campaigns, we must operate under strict constraints. These typically take two forms: knapsack constraints (scalar resource budgets) and matroid constraints (structural rules governing independent selections).
When constraints are introduced, the naive greedy approach fails. Understanding why it fails, and how modern algorithms overcome these failures, reveals the core mechanics of this research direction.
The Challenge of Knapsack Constraints
In a knapsack-constrained problem, every item has an associated cost, and the total cost cannot exceed a fixed budget. As noted by Jing Tang et al. in Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint, the core difficulty lies in navigating the tradeoff between local marginal gains and global budget consumption.
If an algorithm greedily selects items based purely on their absolute marginal utility, it might waste the entire budget on a few cheap, low-value items or a single, excessively expensive item. Conversely, if the algorithm selects items based on density (marginal gain per unit cost), it can still fail spectacularly. For example, consider a budget of 10, one item with a cost of 10 and a value of 10 (density = 1), and another item with a cost of 1 and a value of 1.1 (density = 1.1). A density-based greedy algorithm will pick the second item, leaving a budget of 9, which might not fit any other high-value items, missing out on the superior total value of the first item.
To resolve this, practical frameworks like those proposed by Zeev Nutov et al. in Practical Budgeted Submodular Maximization combine density-greedy selection with partial enumeration. By explicitly guessing a small number of the most critical items in the optimal solution and running the density-greedy algorithm on the remaining budget, the algorithm ensures that high-cost, high-value items are not overlooked. Hau Chan et al. demonstrated in On maximizing a monotone k-submodular function under a knapsack constraint that refining these greedy-with-enumeration strategies yields significantly tighter approximation guarantees than previously assumed.
Historically, reaching the optimal $(1 - 1/e)$ approximation ratio under budget constraints required complex continuous relaxations and rounding techniques, which are computationally prohibitive for large datasets. Alina Ene et al. bypassed this in A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint by designing nearly-linear time combinatorial algorithms that achieve the optimal bound efficiently. Furthermore, when the submodular function exhibits low curvature—meaning the returns do not diminish drastically—Yuichi Yoshida showed in Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint that it is possible to break past the standard $(1 - 1/e)$ barrier by leveraging the bounded rate of decay in marginal gains.
Navigating Matroid Constraints with Non-Oblivious Search
Matroid constraints generalize independent structures, such as ensuring you do not select too many items from the same category (partition matroids). Unlike knapsack constraints, which are scalar budgets, matroids impose strict combinatorial boundaries on which combinations of items are permissible.
If you apply a standard local search algorithm—starting with a valid set and iteratively swapping one item for another to improve the objective value—it can easily get trapped in a poor local optimum. This happens because submodular functions are "oblivious" to the future structural flexibility that an item might provide within the matroid. A swap might look unfavorable in terms of immediate marginal gain, but it could unlock a pathway to a much better global combination later.
To solve this, Yuval Filmus et al. introduced a non-oblivious local search technique in Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search. Instead of evaluating a set $S$ purely by its objective value $f(S)$, the algorithm uses a modified objective function that assigns higher weights to elements based on their marginal contributions to all possible subsets. This mathematical adjustment guides the local search to value elements that preserve structural flexibility, allowing the algorithm to achieve the optimal $(1 - 1/e)$ approximation ratio purely combinatorially. For deterministic settings, Mohit Garg et al. advanced this frontier in Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid by providing the first deterministic algorithm to break the $1/2$ approximation barrier for matroids.
Real-World Multi-Constraint Systems
In complex applications, systems must satisfy multiple types of constraints simultaneously. For instance, in social network advertising, maximizing influence requires optimizing under both matroid constraints (limiting how many ads a single user sees) and knapsack constraints (staying within individual advertiser budgets), as explored by Nan Du et al. in Scalable Influence Maximization for Multiple Products in Continuous-Time Diffusion Networks and Kartik Lakhotia et al. in Approximation Algorithms for Coordinating Ad Campaigns on Social Networks.
By framing these multi-faceted problems through the lens of constrained submodular maximization, researchers can decouple complex domain-specific rules from the optimization engine. Whether managing privacy constraints (Anamay Chaturvedi et al. in Differentially Private Decomposable Submodular Maximization) or strategic agent behavior in online auctions (Andreas Charalampopoulos et al. in A Competitive Posted-Price Mechanism for Online Budget-Feasible Auctions), the underlying geometry of submodularity combined with matroid and knapsack structures provides a robust toolkit for generating provably near-optimal solutions.
Key Foundational Work
Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search (2014) — contributed 2 concept elements to this direction.
Submodular Maximization with Cardinality Constraints (2014) — contributed 1 concept elements to this direction.
Constrained Binary Identification Problem. (2013) — contributed 1 concept elements to this direction.