Deterministic Algorithms for Submodular Maximization

24 concepts20 papers

Submodular functions model the ubiquitous natural phenomenon of diminishing returns: adding an item to a small selection provides greater marginal benefit than adding that same item to a larger selection. Maximizing these functions under constraints is a core problem across machine learning and combinatorial optimization, appearing in data summarization, viral marketing, and sensor placement.

Historically, the most powerful mathematical tools for maximizing submodular functions relied heavily on randomization. However, a recent wave of research has fundamentally shifted this paradigm. By uncovering deep structural properties of submodular relaxations and local search spaces, researchers have designed deterministic algorithms that match or exceed the guarantees of their randomized counterparts, breaking long-standing theoretical barriers without the variance or computational overhead of random sampling.

The Core Tension: Why Randomization Seemed Necessary

To understand why deterministic breakthroughs are significant, we must look at why optimization algorithms turned to randomness in the first place.

For a discrete submodular function $f: 2^V \to \mathbb{R}$, a common theoretical approach is to lift the problem into a continuous domain using the multilinear extension, $F: [0, 1]^V \to \mathbb{R}$. The value of $F(x)$ represents the expected value of $f(S)$ when each element $i \in V$ is sampled independently with probability $x_i$:

$$F(x) = \sum_{S \subseteq V} f(S) \prod_{i \in S} x_i \prod_{i \notin S} (1 - x_i)$$

Continuous greedy algorithms maximize $F(x)$ by taking fractional steps along its gradient, $\nabla F(x)$, and then rounding the final fractional solution to a discrete set.

The bottleneck is computing the gradient $\nabla F(x)$. Because the sum contains $2^{|V|}$ terms, evaluating it exactly is computationally intractable. Randomized algorithms bypass this by using random sampling to approximate the gradient. While highly effective in expectation, this sampling introduces variance, requires a massive number of function queries, and makes the algorithm's behavior unpredictable in practical deployment.

Bypassing Sampling via Structural Insights

Recent work has proven that this reliance on random sampling is not an inherent limitation of the problem. Researchers have developed two primary mechanisms to evaluate or navigate these continuous spaces deterministically.

Exact Evaluation via Sparsity

Instead of trying to approximate the gradient across the entire dense continuous cube, what if we could evaluate the multilinear extension exactly on specific, well-structured vectors?

In Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization, Niv Buchbinder introduced the Extended Multilinear Extension. The core insight is that if a continuous relaxation is evaluated strictly over sparse vectors, the exponential number of terms collapses into a mathematically tractable formula. This allows the algorithm to evaluate the continuous relaxation exactly and deterministically at each step. By doing so, Niv Buchbinder provided the first deterministic algorithm for non-monotone submodular maximization under matroid constraints that achieves an approximation ratio of $1/e - \epsilon$, completely matching the performance of state-of-the-art randomized approaches.

An alternative to continuous gradient ascent is discrete local search, where an algorithm starts with a valid set and iteratively swaps elements to improve the objective value. However, standard local search is "oblivious"—it only evaluates the immediate marginal gain of a swap, which frequently causes it to get trapped in poor local optima.

To solve this deterministically, Niv Buchbinder utilized a "non-oblivious" local search strategy in Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint. Instead of optimizing the submodular function $f(S)$ directly, the local search optimizes a modified, weighted objective function. This non-oblivious objective artificially weights elements based on their potential to combine beneficially with elements chosen in future steps. This structural adjustment guides the deterministic search path away from local traps, achieving the optimal $1 - 1/e$ approximation ratio for monotone submodular functions under general matroid constraints without a single random sample.

Breaking Through Classical Ceilings

For decades, certain approximation ratios were viewed as insurmountable ceilings for deterministic or highly efficient algorithms. Recent structural insights have systematically broken these barriers.

Breaking the 1/2 Barrier for Matroids

For a monotone submodular function subject to a matroid constraint, the classical deterministic greedy algorithm yields a $1/2$-approximation. Breaking this $1/2$ barrier deterministically was a long-standing open question.

Mohit Garg et al. achieved this by developing a deterministic $(1/2 + \epsilon)$-approximation algorithm. The intuition behind their approach is to combine standard greedy choices with a look-ahead mechanism. By analyzing the structural properties of the matroid, the algorithm identifies and avoids the specific worst-case configurations that traditionally bound the greedy algorithm to $1/2$.

Surpassing 1/e for Non-Monotone Functions

When a submodular function is non-monotone—meaning the addition of an element can cause the total value to decrease—optimization becomes significantly harder. For a long time, $1/e \approx 0.368$ was considered a natural performance ceiling for general constraints.

Approximation Ratio Milestones (Non-Monotone Constraints)
|
|-- 0.401  [Buchbinder (2023)] - Tighter DR-submodular damage bounds
|-- 0.385  [Tukan et al. (2024)] - Practical O(n + k²) scale
|-- 0.372  [Ene et al. (2016)] - First to break the 1/e barrier
|-- 0.368  (1/e Classical Limit)
v

Alina Ene et al. first proved that $1/e$ is not a fundamental limit, breaking the barrier with a hybrid algorithm that achieved a $0.372$ approximation ratio. Building on this direction, Niv Buchbinder pushed the theoretical bound further to $0.401$ in Constrained Submodular Maximization via New Bounds for DR-Submodular Functions. This was achieved by deriving a tighter mathematical bound for the "damage" or marginal loss incurred when non-monotone functions fluctuate, narrowing the gap toward the theoretical inapproximability limit of $0.478$.

Bridging Theory and Practice

While many barrier-breaking algorithms remain theoretical due to high polynomial query complexities, recent work has successfully translated these high-performance bounds into practical, scalable code.

Murad Tukan et al. developed a practical algorithm that achieves a $0.385$-approximation for non-monotone functions under a cardinality constraint. They bypassed the traditional performance-speed trade-off by pairing an accelerated local search with a guided stochastic greedy framework. This combination maintains an exceptionally low query complexity of $O(n + k^2)$, proving that barrier-breaking approximations can be deployed efficiently on large-scale real-world datasets.

Algorithmic Pruning and Complex Constraints

As the field has matured, these deterministic principles have been extended to handle specialized function classes and complex real-world constraints.

The Power of Deferred Deletion

For symmetric submodular functions—where the value of a set equals the value of its complement ($f(S) = f(V \setminus S)$)—Zongqi Wan et al. demonstrated that deterministic frameworks can match or exceed randomized results by incorporating a simple DELETE procedure into standard greedy frameworks.

Because non-monotonicity means early greedy selections can become liabilities as the set grows, the DELETE procedure systematically evaluates whether removing an element restores more value than adding a new one. This simple, deterministic pruning step eliminates the need for unpredictable sampling-based continuous methods in large-scale data summarization tasks.

Scaling to Knapsack and Packing Constraints

In many practical applications, items have varying costs, leading to knapsack or linear packing constraints rather than simple cardinality bounds.

By replacing random sampling with precise structural insights—such as sparse continuous evaluations, non-oblivious objectives, and deferred deletion—modern submodular optimization provides the best of both worlds: the rigorous guarantees of optimal approximation theory alongside the predictability and speed of deterministic execution.

Key Foundational Work

Non-monotone submodular maximization under matroid and knapsack constraints (2009) — contributed 1 concept elements to this direction.
Efficient Submodular Function Maximization under Linear Packing Constraints (2012) — 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_deterministic_submodular_maximization_2433af5e,
  title = {deterministic submodular maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/deterministic-submodular-maximization/rdr_2433af5ec0424e94b9deae5323c73201},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_deterministic_submodular_maximization_2433af5e_v1,
  title = {deterministic submodular maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/deterministic-submodular-maximization/rdr_2433af5ec0424e94b9deae5323c73201/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}

See something wrong? Report a mistake