Submodular functions formalize the intuitive concept of diminishing returns: the marginal benefit of adding an item to a collection decreases as the collection grows. Mathematically, a function $f: 2^V \to \mathbb{R}$ is submodular if for all subsets $A \subseteq B \subseteq V$ and any element $x \notin B$:
$$f(A \cup \{x\}) - f(A) \ge f(B \cup \{x\}) - f(B)$$
For decades, the standard assumption in combinatorial optimization was that these functions were also monotone—meaning that adding an element never hurts the total value ($f(A) \le f(B)$). Under monotonicity, a simple greedy algorithm that repeatedly selects the element with the highest marginal gain provides excellent approximation guarantees.
However, many real-world problems are inherently non-monotone. In these settings, adding an element can actually decrease the overall objective value.
The Intuition Behind Non-Monotonicity
Why would more items yield less value? Consider three practical scenarios:
- Data and Video Summarization: As explored by Jia Xu et al. in Gaze-enabled egocentric video summarization via constrained submodular maximization, a good summary must be both representative and concise. If you keep adding video frames indefinitely, you introduce redundancy and noise, spoiling the utility of the summary.
- E-Commerce Assortment Selection: In revenue models, displaying too many items can overwhelm or distract a user. As noted by Mingdong Ou et al. in Multinomial Logit Bandit with Linear Utility Functions, low-quality items can cannibalize the attention meant for high-value options, causing the total expected reward to decline.
- System Upgrades: When transitioning between infrastructure states, adding new components while decommissioning old ones can cause system performance to fluctuate or drop temporarily, as shown by Max Klimm et al. in Incremental-Decremental Maximization.
In all these cases, the global maximum is not found at the boundary of the constraints, but somewhere in the interior.
Monotone Objective: Non-Monotone Objective:
Value Value
^ ^
| /--- | /---\
| / | / \
| / | / \
+----------> +---------->
Set Size Set Size
(More is always better) (Over-inclusion hurts)
Why the Classic Greedy Algorithm Fails
The classic greedy algorithm fails in non-monotone settings because it is short-sighted. If an algorithm blindly picks the element with the largest immediate marginal gain, it can easily trap itself in a suboptimal state.
Worse yet, as highlighted by Richard Santiago and Yuichi Yoshida in Weakly Submodular Function Maximization Using Local Submodularity Ratio, a greedy algorithm might encounter a situation where every available element provides a negative marginal contribution. If the algorithm is forced to satisfy a fixed set-size constraint, it will be compelled to actively destroy the value of its own solution.
To maximize non-monotone functions, algorithms must know when to stop and how to avoid toxic elements that look good initially but ruin future flexibility.
Paradigm 1: Continuous Relaxation and Rounding
One of the most mathematically rigorous ways to solve this problem is to transform the discrete selection problem into a continuous one. This is known as the relax-and-round framework.
The Multilinear Extension
Instead of deciding whether to include an item ($x_i \in \{0, 1\}$), we assign each item a probability $x_i \in [0, 1]$. The discrete function $f(A)$ is extended to a continuous function $F(x)$, which represents the expected value of $f$ if each element $i$ is sampled independently with probability $x_i$.
Contention Resolution Schemes
Once an optimal fractional point $x$ is found within a continuous polytope, the challenge is mapping it back to a valid discrete set. Independent sampling might violate hard constraints (e.g., picking 6 items when the budget is 5).
To solve this, Chandra Chekuri et al. introduced Contention Resolution (CR) Schemes in Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes. A CR scheme takes a random sample from the fractional solution and drops conflicting elements in a controlled, randomized way. This ensures that the final discrete set remains feasible while preserving a constant fraction of the continuous solution's value.
Using these continuous relaxations, Alina Ene et al. broke the long-standing $1/e$ approximation barrier for non-monotone functions under general constraints in Constrained Submodular Maximization: Beyond 1/e. Later, Niv Buchbinder pushed this boundary even further to a $0.401$-approximation in Constrained Submodular Maximization via New Bounds for DR-Submodular Functions.
Paradigm 2: Fast Combinatorial and Greedy Variants
While continuous methods provide excellent theoretical guarantees, evaluating the multilinear extension requires extensive sampling, making it computationally expensive for massive datasets. To bypass this, researchers designed purely discrete, combinatorial algorithms that modify the greedy strategy to handle non-monotonicity.
1. Interlaced and Alternating Greedy
If a single greedy path gets trapped by negative marginal gains, why not run two? In Interlaced Greedy Algorithm for Maximization of Submodular Functions in Nearly Linear Time, Alan Kuhnle proposed running two greedy procedures concurrently. By alternating selections between them, the algorithm maintains a safety net: if one path falls into a trap of negative returns, the other path balances it out, achieving a $1/4 - \epsilon$ approximation in nearly linear time.
2. Stochastic Sampling (SampleGreedy)
Another way to prevent the algorithm from making catastrophic early choices is to inject randomness. In Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint, Federico Fusco et al. introduced SampleGreedy. Instead of looking at all available elements, the algorithm randomly samples a small subset of elements at each step and picks the best from that sample. This simple randomization prevents the algorithm from over-allocating early on and naturally protects it from saturation.
3. Guided Local Search
To match the performance of continuous methods without their computational cost, Yixin Chen et al. developed a hybrid approach in Discretely beyond 1/e: Guided Combinatorial Algortihms for Submodular Maximization. They used a fast local search to "guide" a greedy search, successfully breaking the $1/e$ barrier using purely combinatorial operations.
Paradigm 3: Streaming and Dynamic Environments
In modern big data applications, data often arrives as a continuous stream, or changes dynamically over time, meaning algorithms cannot afford to store the entire dataset in memory.
Streaming Thresholds
In a single-pass stream, decisions are irrevocable. If you accept too many items early on, you might run out of budget or accumulate negative marginal utility. To solve this, Chandra Chekuri et al. in Streaming Algorithms for Submodular Function Maximization combined value thresholding with randomized buffering. By only accepting elements that exceed a dynamically computed marginal utility threshold, the algorithm filters out clutter and avoids early saturation.
Parallel Adaptivity
When processing massive datasets in parallel, we want to minimize the number of sequential rounds (adaptivity). Georgios Amanatidis and Federico Fusco designed PARKNAPSACK in Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity. To handle non-monotonicity in parallel, they built explicit stopping conditions based on the accumulation of negative marginal gains, ensuring the parallel rounds terminate before detrimental additions compromise the solution quality.
Key Foundational Work
Non-monotone submodular maximization under matroid and knapsack constraints (2009) — contributed 2 concept elements to this direction.