Submodular Maximization under Matroid and Knapsack Constraints

This direction is merged into another direction: constraint generalization. Its last version stays readable and citable here.

Version 1 of 119 papers19 conceptsfrozen 2026-10-04

In many real-world selection problems, the value of adding an item to a collection depends on what is already there. This is the principle of diminishing returns: the first sensor placed in a forest provides a wealth of new data, but the hundredth sensor likely covers ground already monitored by its neighbors. Mathematically, this is captured by submodular functions.

While maximizing submodular functions under a simple "pick $k$ items" constraint is well-understood, modern applications—from migrant resettlement to diverse news recommendation—require far more complex rules. Researchers are now focused on maximizing these functions under structured constraints, such as matroids and knapsacks, which model sophisticated requirements like diversity, hierarchy, and budget limits.

The Geometry of Constraints

A simple cardinality constraint (picking $k$ items) is a uniform requirement. However, as Andreas Krause and Matthew J. Streeter highlight in their work on online submodular maximization, real-world tasks often involve matroid constraints.

Think of a matroid as a way to ensure diversity across different categories. If you are hiring a team, you might have a total budget (a knapsack constraint) but also a requirement that you cannot hire more than two people from the same specialty (a partition matroid). These constraints are more difficult because a greedy algorithm that looks only at the next best item might "trap" itself, picking an item that satisfies a local limit but prevents it from picking a much more valuable set of items later.

To address this, Kai Han and colleagues developed deterministic algorithms that can handle non-monotone functions—where adding an item might actually decrease the total value—over matroid constraints in nearly linear time. This is a significant leap for large-scale systems where "strong but slow" algorithms are impractical.

Beyond Pure Submodularity

Not every objective function is perfectly submodular. Some functions only approximately exhibit diminishing returns. This has led to the study of weakly submodular functions.

Lin Chen and Amin Karbasi explored whether randomization helps greedy algorithms when facing these "imperfect" functions under matroid constraints. By adding a layer of randomness, the algorithm avoids getting stuck in local optima caused by the interaction between the weak submodularity and the complex matroid structure.

Taking this further, Theophile Thiery and Justin Ward introduced two-sided weak submodularity. By bounding how much a function deviates from submodularity when elements are both added and removed, they provided much tighter guarantees for problems like sparse linear regression, where the goal is to select a small, informative subset of features.

Robustness in Uncertain Environments

In practice, the set of available items might change. An adversarial actor might delete your best sensors, or a user might suddenly become unavailable. This necessitates robust submodular maximization.

Nima Anari, Sebastian Pokutta, and Mohit Singh have pioneered bi-criteria approaches to this problem. Instead of trying to find a single perfect set that satisfies the constraint, they allow the algorithm to select a slightly larger union of sets. This relaxation provides a "safety net," ensuring that even if some items are removed, the remaining set is still near-optimal.

For streaming data or adversarial deletions, Paul Duetting and Silvio Lattanzi showed that it is possible to maintain a small summary of data that remains robust to deletions, even under general matroid constraints. This allows for efficient optimization in dynamic environments without needing to recompute the entire solution from scratch.

From Theory to Application

These mathematical frameworks solve high-stakes allocation problems. For instance, Dan-Xuan Liu and Chao Qian applied matroid-constrained submodular maximization to migrant resettlement. Here, the "diminishing returns" represent the saturation of local job markets, while the "matroid constraints" ensure that each migrant is assigned to exactly one location and that no location exceeds its capacity.

Similarly, in the world of online learning, Baosheng Yu and Dacheng Tao developed linear submodular bandits that respect knapsack constraints. This allows a recommendation system to maximize the diversity of news topics shown to a user while strictly adhering to a "budget" of the user's limited attention span.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_submodular_maximization_under_matroid_an_2b08f7e3,
  title = {Submodular Maximization under Matroid and Knapsack Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/submodular-maximization-under-matroid-and-knapsack-constraints/rdr_2b08f7e3af934c15a146a52a79e3b471},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_submodular_maximization_under_matroid_an_2b08f7e3_v1,
  title = {Submodular Maximization under Matroid and Knapsack Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/submodular-maximization-under-matroid-and-knapsack-constraints/rdr_2b08f7e3af934c15a146a52a79e3b471/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}