Non-Monotone Submodular Maximization

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

Version 1 of 2274 papers321 conceptsfrozen 2026-10-04

In the landscape of discrete optimization, submodularity is often described as the "discrete analog" of convexity or concavity. It captures the intuitive law of diminishing returns: adding an element to a small set provides more marginal benefit than adding that same element to a larger set.

For years, the gold standard for solving these problems was the simple greedy algorithm. If your objective function is monotone—meaning adding more items always increases or maintains the total value—the greedy approach is remarkably effective. However, a significant body of research has shifted focus toward a more difficult and realistic regime: non-monotone submodular maximization.

The Problem of "Too Much of a Good Thing"

In many real-world scenarios, the assumption that "more is always better" fails. Consider document summarization: as you add more sentences to a summary, the utility initially grows. But eventually, the summary becomes bloated, redundant, and less useful. The total value peaks and then declines. This is the essence of non-monotonicity.

As noted in Learning and Optimization with Submodular Functions, while greedy algorithms provide strong guarantees for monotone functions, they often fail when the objective is non-monotone. The challenge is that a standard greedy algorithm is "short-sighted." It might pick an element that offers a high immediate gain but eventually forces the set into a region where every subsequent addition has a massive negative marginal gain, as explored by Shaojie Tang and Jing Yuan in their work on sequential submodular maximization.

Strategic Selection and the Double Greedy

To handle non-monotonicity, researchers have moved beyond simple incremental growth. One of the most influential breakthroughs was the "double greedy" framework. Instead of starting from an empty set and adding items, or starting from a full set and removing them, double greedy algorithms maintain two sets—one growing from the bottom up and one shrinking from the top down—and coordinate them to find a middle ground.

Xinghao Pan extended this logic in Parallel Double Greedy Submodular Maximization, using concurrency control to scale these problems to massive graphs. Similarly, the FastInterlaceGreedy (FIG) algorithm, described in Nearly Linear-Time, Deterministic Algorithm for Maximizing (Non-Monotone) Submodular Functions Under Cardinality Constraint, "interlaces" two greedy procedures to ensure the algorithm doesn't get trapped in the local minima created by negative marginal gains.

Scaling to Big Data: Parallelism and Adaptivity

As datasets grow, the sequential nature of greedy algorithms becomes a bottleneck. The research direction has pivoted toward low-adaptivity algorithms—methods that can pick large batches of items in parallel rather than one by one.

Alan Kuhnle has been a key figure in this transition, developing nearly linear-time parallelizable algorithms that achieve constant-factor approximations in just $O(\log n)$ rounds. This is achieved by identifying "thresholds" of utility; instead of picking the absolute best item, the algorithm picks any item that exceeds a certain quality threshold, allowing for massive parallelization without sacrificing theoretical guarantees. Kai Han and colleagues further refined this for complex constraints like knapsacks in Practical Parallel Algorithms for Submodular Maximization.

Breaking the 1/e Barrier

For a long time, the $1/e \approx 0.367$ approximation ratio was considered a fundamental barrier for non-monotone submodular maximization under a size constraint. Achieving anything better usually required "continuous relaxation"—a computationally expensive process of treating discrete items as continuous variables and then rounding them back.

Recent work by Ankur Nath, Yixin Chen, and Alan Kuhnle has finally broken this barrier using purely combinatorial (discrete) methods. In Discretely Beyond 1/e: Guided Combinatorial Algorithms for Submodular Maximization, they introduce a "guided" approach where a fast local search informs a randomized greedy process. This allows the algorithm to "see" the potential for future value degradation and avoid exhausting high-value elements too early.

Robustness and Adversarial Objectives

Finally, the field has expanded to consider robustness. In many applications, we don't just want to maximize one function; we want to perform well even if an adversary chooses which objective we are evaluated on.

Andreas Krause, Brendan McMahan, and Carlos Guestrin addressed this with the SATURATE algorithm in Selecting Observations against Adversarial Objectives. They demonstrated that while the minimum of several submodular functions is not itself submodular, specialized algorithms can still provide strong guarantees by slightly relaxing the budget constraints. This ensures that the selection is balanced and robust against the worst-case scenario.

Papers in this version

Showing 60 of 274 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_non_monotone_submodular_maximization_436edbe9,
  title = {non-monotone submodular maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-monotone-submodular-maximization/rdr_436edbe9f3034e1a9dc253730439978c},
  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_non_monotone_submodular_maximization_436edbe9_v1,
  title = {Non-Monotone Submodular Maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-monotone-submodular-maximization/rdr_436edbe9f3034e1a9dc253730439978c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}