Dual-Set Tracking for Non-Monotone Submodular Maximization

19 concepts14 papers1 proposal

Submodular functions are the mathematical workhorses of combinatorial optimization, capturing the natural law of diminishing returns: adding an item to a small selection yields a larger marginal benefit than adding that same item to a larger selection. When a submodular function is monotone, meaning that adding items can never decrease the total value, a simple greedy algorithm works remarkably well. At each step, you simply pick the item that provides the highest marginal gain.

However, many real-world problems are non-monotone. In social network marketing, adding too many influencers might exhaust a budget or alienate users, causing total reach to drop. In data summarization, adding redundant data points can dilute the quality of a summary. For non-monotone functions, adding an item can yield a negative marginal gain.

This introduces a severe challenge for standard greedy optimization. A classic greedy algorithm can easily get trapped: it might greedily select an item that offers high immediate value, only to discover later that this choice destroys the value of the remaining set or blocks a much better combination of future items.

To bypass this trap, a powerful algorithmic paradigm has emerged: dual-set tracking. Instead of maintaining a single growing solution, these algorithms maintain two or more candidate sets simultaneously. By evaluating choices across multiple sets, the algorithms hedge against the pitfalls of non-monotonicity and guarantee robust, high-quality solutions in linear or nearly linear time.


The Core Intuition: Bi-Directional Evolution

The foundational manifestation of dual-set tracking is the "double greedy" framework. To understand why it works, imagine trying to find an optimal subset from a ground set of items. Instead of starting from nothing and building upward, a bi-directional algorithm maintains two distinct sets throughout its execution:

  1. Set $A$ (The Floor): Initialized as the empty set ($\emptyset$). It grows over time as elements are permanently added.
  2. Set $B$ (The Ceiling): Initialized as the entire ground set ($V$). It shrinks over time as elements are permanently removed.

The algorithm iterates through every element in the ground set exactly once. For each element $e$, it computes two marginal gains: the gain of adding $e$ to the growing set $A$, and the gain (or loss) of removing $e$ from the shrinking set $B$.

Initial State:
Set A (Growing): [ ]
Set B (Shrinking): [ e1, e2, e3, e4, e5 ]

Step-by-step decision for each element:
Evaluate element against both sparse context (A) and dense context (B)
  ├── Add to A? ──> Set A expands
  └── Remove from B? ──> Set B contracts

Final State:
Set A == Set B  (They converge to the same optimized solution)

As shown by Joseph Naor et al. in A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization, this simple mechanism guarantees a tight $1/2$-approximation ratio in linear time.

Why does this dual evaluation prevent the algorithm from getting trapped? The secret lies in submodularity itself. Because $A$ is always a subset of $B$ ($A \subseteq B$), the marginal gain of adding an element to $A$ is mathematically bounded by the marginal changes in $B$. If an element has a negative marginal utility when added to $A$, submodularity dictates that keeping it in the larger set $B$ is even worse. Therefore, removing it from $B$ must yield a relative benefit.

By forcing every element to be evaluated against both a sparse context ($A$) and a dense context ($B$), the algorithm balances competing components. Kobi Bodek leverages this bi-directional refinement in Maximizing Sums of Non-monotone Submodular and Linear Functions: Understanding the Unconstrained Case to optimize composite functions containing both submodular and linear regularizers. Similarly, Moran Feldman demonstrates in Maximizing Symmetric Submodular Functions that when the underlying function is symmetric, this dual-set convergence can be exploited to achieve even higher approximation ratios.


Parallel Disjoint Sets: Creating Fallback Paths

While the bi-directional approach works perfectly for unconstrained problems, it encounters a major hurdle when complex constraints (such as knapsack or matroid constraints) are introduced. If you initialize Set $B$ as the full ground set, you immediately violate your constraints from step one, making it impossible to evaluate valid marginal gains during the shrinking process.

To solve this, researchers adapted the dual-set architecture to maintain multiple parallel, disjoint growing sets rather than opposing ones.

Consider the interlaced greedy approach introduced by Alan Kuhnle in Interlaced Greedy Algorithm for Maximization of Submodular Functions in Nearly Linear Time. Instead of building a single solution, the algorithm runs two greedy procedures concurrently, alternating selections to build two disjoint candidate sets.

If a high-value element threatens to become a "trap"—meaning it looks lucrative now but will cause severe negative marginal returns for subsequent choices—the parallel architecture isolates the damage. The algorithm routes elements dynamically:

Incoming Element ──> Evaluate Marginal Gain in Set 1 vs. Set 2
                        ├── Higher gain in Set 1 ──> Allocate to Set 1
                        └── Higher gain in Set 2 ──> Allocate to Set 2

This strategy is formalized by Kai Han et al. in Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time. By maintaining two disjoint candidate sets and placing each element into the set where it provides the highest marginal utility, the authors create a deterministic mapping between the choices of the algorithm and the optimal solution. This mapping ensures that any utility loss caused by non-monotonicity is strictly bounded.

Under knapsack constraints, Canh V. Pham et al. in Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint and Canh V. Pham in Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity demonstrate that parallel greedy paths serve as an essential fallback mechanism. If one path gets trapped by elements that eventually trigger diminishing or negative returns, the alternative disjoint set remains uncorrupted, preserving a high-value solution.


Generalization Across Domains

The core philosophy of dual-set tracking—hedging against non-monotone value drops by maintaining redundant or opposing solution paths—has proven to be highly adaptable across diverse optimization landscapes.

Streaming and Robustness

In data streaming environments, items arrive sequentially, and some may be unexpectedly deleted. Kai Han et al. show in Deletion-Robust Submodular Maximization with Knapsack Constraints that maintaining multiple disjoint candidate solutions simultaneously provides a built-in "warehouse" of alternatives. If an adversarial deletion wipes out elements from one candidate set, the system instantly recovers a high-quality solution from the remaining sets. For submodular cover problems, Victoria G. Crawford demonstrates in Scalable Bicriteria Algorithms for Non-Monotone Submodular Cover that tracking multiple disjoint sets based on their marginal utility-to-cost ratios prevents redundant items from saturating the selection process.

Continuous Optimization

The strategy translates directly from discrete sets to continuous spaces. In Optimal Continuous DR-Submodular Maximization and Applications to Provable Mean Field Inference, Yatao Bian et al. introduce a continuous double-greedy algorithm. To maximize non-monotone diminishing-returns (DR) submodular functions, the algorithm tracks two concurrent solution trajectories—one starting at the lower bound and one at the upper bound—updating them via convex combinations of their marginal gradients to achieve an optimal $1/2$-approximation in a single pass.

Bandit Feedback and Game Theory

When operating with zero prior knowledge under full-bandit feedback, Fares Fourati et al. show in Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback that dual-set tracking allows an agent to effectively balance exploration and exploitation, successfully navigating negative rewards. In multi-agent competitive environments, Stefano Leonardi 0001 et al. demonstrate in Algorithmically Fair Maximization of Multiple Submodular Objective Functions that when agents maintain two concurrent candidate sets, they can successfully hedge against value loss caused by their competitors' choices, ensuring fair and efficient resource allocation.

Parallelization and Mechanism Design

To break the sequential bottleneck inherent to traditional greedy algorithms, Alan Kuhnle et al. design a bifurcated approach in Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint. By maintaining one set dedicated entirely to filtering the search space and another for building the actual solution, they enable fast, parallelized pruning of massive datasets. Finally, in the realm of mechanism design, Kai Han et al. utilize dual candidate sets in Triple Eagle: Simple, Fast and Practical Budget-Feasible Mechanisms to maintain robust winner selections even when individual seller contributions fluctuate unpredictably.

By moving away from a single, short-sighted greedy path and adopting a multi-set tracking architecture, these algorithms transform non-monotone submodular maximization from an unpredictable hazard into a highly controllable, theoretically optimal, and scalable optimization process.

Key Foundational Work

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization (2015) — contributed 2 concept elements to this direction.
Maximizing Symmetric Submodular Functions (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_disjoint_candidate_set_maintenance_9fe2e192,
  title = {disjoint candidate set maintenance},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/disjoint-candidate-set-maintenance/rdr_9fe2e1922e4e444fa5211d1d15d312e5},
  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_disjoint_candidate_set_maintenance_9fe2e192_v1,
  title = {disjoint candidate set maintenance},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/disjoint-candidate-set-maintenance/rdr_9fe2e1922e4e444fa5211d1d15d312e5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake