Submodular maximization is often described as the discrete analogue of convex optimization. At its heart is the property of diminishing returns: adding an element to a small set provides more marginal gain than adding it to a large one. In many classic problems, like sensor placement or document summarization, we assume the function is monotone—more is always better.
However, real-world objectives are often non-monotone. In social network influence, adding too many influencers might lead to "marketing fatigue" or redundant costs that outweigh the reach. In these cases, the objective function can decrease as the set grows. Traditional greedy algorithms, which blindly pick the best available item, fail here because they can easily fall off a "utility cliff" where every subsequent choice destroys value.
To solve this, a powerful family of algorithms has emerged that replaces the single greedy path with a dual-set strategy. By maintaining two disjoint candidate solutions simultaneously, these algorithms hedge against the risks of non-monotonicity.
The Intuition of Hedging
In a standard greedy algorithm, you start with an empty set and add the element with the highest marginal gain. If the function is non-monotone, you might eventually be forced to add elements that have negative marginal gains just to satisfy a constraint, or you might pick an element early on that prevents you from picking a much better combination later.
The dual-set approach, exemplified by the FastInterlaceGreedy (FIG) algorithm developed by Alan Kuhnle in Nearly Linear-Time, Deterministic Algorithm for Maximizing (Non-Monotone) Submodular Functions Under Cardinality Constraint, changes the game. Instead of building one solution, the algorithm maintains two disjoint sets, $S_1$ and $S_2$. When a new element is considered, the algorithm evaluates its marginal gain for both sets and assigns it to the one where it performs better.
This creates a "theoretical safety net." If the utility of $S_1$ begins to decrease because of the non-monotone nature of the function, the potential value is often captured by $S_2$. As Canh V. Pham and colleagues note in Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint, this structure prevents the greedy process from becoming trapped by locally optimal elements that might negatively impact the final set's utility.
Bidirectional Convergence
Another facet of this dual-set logic is the Double Greedy framework. Instead of building two sets from the ground up, this method approaches the optimal solution from two different directions.
In Non-monotone DR-Submodular Function Maximization, Tasuku Soma and Yuichi Yoshida describe a bidirectional greedy optimization. One process starts with an empty set (the lower bound) and another starts with the full ground set (the upper bound). The algorithm moves these two "bounds" toward each other.
Think of it as a pincer movement:
- The "empty" set tries to grow by adding elements with high gains.
- The "full" set tries to shrink by removing elements that cause the most harm (or provide the least gain).
By evaluating the marginal utility of both adding and removing at each step, the algorithm balances the risk. This is particularly effective for DR-submodular functions (diminishing return submodular functions on integer lattices), where the "coordinates" of your solution can be more than just 0 or 1.
Parallelism and Filtering
The dual-set mechanism also solves a major practical hurdle: parallelization. Standard greedy algorithms are inherently sequential—you can't pick the second item until you know the first.
Alan Kuhnle introduced the AST (Alternate Threshold) and ATG algorithms in Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization to address this. These algorithms use a bifurcated approach:
- Set A (The Filter): Scans the ground set to identify potential candidates.
- Set B (The Solution): Builds the actual solution using only elements that maintain a high average marginal gain.
By separating filtering from construction, the algorithm ensures that individual elements with negative marginal gains do not degrade the overall quality of the selection during parallel processing. This "alternate thresholding" strategy, further refined by Canh V. Pham in Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint, allows for near-optimal $O(\log n)$ adaptivity, meaning the algorithm can run in very few sequential rounds even on massive datasets.
Why It Works: The Mapping Argument
The mathematical "magic" behind why two sets are better than one lies in the ability to map the elements of an optimal solution ($OPT$) to the algorithm's choices.
In Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time, Kai Han and co-authors explain that by maintaining two disjoint sets, you can ensure that for every element in the optimal solution, there is a "path" for it to be captured by at least one of the two sets. If a greedy choice in Set 1 prevents an optimal element from being added there, the dual-set structure ensures that the utility loss is bounded because Set 2 remains an available destination.
This deterministic mapping provides a robust alternative to randomized algorithms. While randomized greedy methods often achieve good expected results, dual-set mechanisms like QuickSwap, proposed by Eric Balkanski and Alan Kuhnle in Submodular Maximization in Exactly n Queries, provide guaranteed performance ratios (like $1/4$) using a minimal number of queries.
Summary
The shift from single-set greedy selection to dual-set mechanisms represents a fundamental evolution in discrete optimization. By maintaining two disjoint sets, researchers have found a way to:
- Hedge against the value drops inherent in non-monotone functions.
- Parallelize optimization by separating filtering from selection.
- Guarantee performance deterministically, even in high-velocity streaming environments or complex auction mechanisms.