Diverse Subset Selection via Submodular Maximization

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2143 papers198 conceptsfrozen 2026-10-04

In many domains of computer science, we are faced with the "firehose" problem: we have a massive collection of items—search results, video frames, sensor locations, or protein sequences—but we can only present or process a tiny fraction of them. The challenge is not just to find the "best" items, but to find a diverse subset that covers as much information as possible without being redundant.

Traditional approaches often rank items by individual quality scores. However, as M. J. V. Streeter and Andreas Krause argue in Online Learning of Assignments, this fails because the value of an item depends on what has already been selected. If a search engine returns ten identical (but high-quality) links, the user gains nothing after the first one.

The research direction across these 114 papers centers on using submodular functions to mathematically formalize this intuition of "diminishing returns" for subset selection.

The Intuition: Diminishing Returns

At the heart of this research is the property of submodularity. A set function $f$ is submodular if, for any two sets $A \subseteq B$ and an item $x \notin B$, the marginal gain of adding $x$ to the smaller set is at least as large as the marginal gain of adding it to the larger set:

$$f(A \cup \{x\}) - f(A) \geq f(B \cup \{x\}) - f(B)$$

In plain English: the more you already know, the less a new piece of information surprises you.

This property is a natural fit for diversity. In Summarization Through Submodularity and Dispersion, Anirban Dasgupta and Ravi Kumar show that by modeling text summarization as a submodular objective, the system naturally avoids redundant sentences. Once a specific topic is "covered" by the summary, the marginal utility of similar sentences drops, forcing the algorithm to look for sentences that cover unrepresented themes.

Why It Works: The Greedy Guarantee

While finding the absolute optimal subset is often NP-hard, submodular functions possess a remarkable property: they can be solved near-optimally using a simple greedy algorithm.

If you start with an empty set and repeatedly add the item that provides the largest marginal gain, you are guaranteed to achieve at least $(1 - 1/e) \approx 63\%$ of the optimal value. As shown in Online Learning of Assignments that Maximize Submodular Functions by Daniel Golovin and Andreas Krause, this "no-regret" framework allows systems to learn these assignments online, adapting to user clicks while maintaining theoretical performance bounds.

Applications Across the Stack

The power of this framework lies in its versatility. Researchers have applied submodular optimization to solve "coverage" problems in vastly different fields:

Balancing Coverage and Dispersion

While submodularity handles coverage well, some problems require an even stricter push for variety. Anirban Dasgupta and colleagues introduced the idea of combining submodular functions with dispersion functions—which explicitly maximize the distance between selected items.

In Query-Focused Opinion Summarization, this hybrid approach ensures that a summary isn't just "covering" the main points, but is also spreading its selections across the widest possible range of perspectives. This balance is what allows modern recommendation systems, like the one proposed by Liangwei Yang in DGRec, to break "filter bubbles" by prioritizing diverse neighbor selection in graph neural networks.

Conclusion

The shift toward submodular optimization represents a move away from "black-box" heuristics toward a principled, axiomatic way of defining what a "good" subset looks like. By treating diversity as a mathematical consequence of diminishing returns, researchers have created a unified toolkit for summarization, recommendation, and data efficiency that is both theoretically grounded and practically robust.

Papers in this version

Showing 60 of 143 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 133 papers
  2. Version 1 · 2026-10-04 · 143 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_submodular_diversity_optimization_82b44010,
  title = {submodular diversity optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/submodular-diversity-optimization/rdr_82b44010991f490ba8b374d9fbc91410},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_diverse_subset_selection_via_submodular__82b44010_v1,
  title = {Diverse Subset Selection via Submodular Maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/diverse-subset-selection-via-submodular-maximization/rdr_82b44010991f490ba8b374d9fbc91410/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}