Submodular Sandwich Approximation for Non-Submodular Optimization

26 concepts21 papers1 proposal

In discrete optimization, submodularity is the gold standard for tractability. It formalizes the intuitive law of diminishing returns: adding an element to a small set provides greater incremental benefit than adding the same element to a larger set. When an objective function is submodular and monotonic, a simple greedy algorithm—which repeatedly selects the element with the highest marginal gain—is guaranteed to find a solution within a factor of $(1 - 1/e) \approx 63\%$ of the global optimum.

Unfortunately, real-world systems frequently break this property. Consider viral marketing or misinformation containment on social networks. If a user requires multiple friends to recommend a product before they buy it, the system exhibits supermodular compounding effects rather than diminishing returns. When submodularity is lost, the standard greedy guarantee vanishes, and direct optimization typically becomes computationally intractable.

To bridge this gap, researchers have developed the Submodular Sandwich Approximation framework. The core intuition is simple: if you cannot optimize a non-submodular function directly, trap it between two submodular functions that you can optimize.

  Upper Bound U(S)  [Submodular: Easy to optimize]
     ▲
     │   True Objective f(S)  [Non-Submodular: Hard to optimize]
     ▼
  Lower Bound L(S)  [Submodular: Easy to optimize]

The Core Mechanism: Trapping the Objective

Suppose we want to maximize a non-submodular, monotonic set function $f(S)$ subject to a size constraint $|S| \le k$. The sandwich framework operates by constructing two monotonic submodular functions—a lower bound $L(S)$ and an upper bound $U(S)$—such that for any valid set $S$:

$$L(S) \le f(S) \le U(S)$$

Instead of optimizing $f(S)$ directly, we execute a greedy selection process on these submodular bounds. For example, if we run the greedy algorithm on the lower bound $L(S)$, we obtain a solution set $S_L$. Because $L(S)$ is submodular, we know that $L(S_L)$ is a good approximation of the optimal solution for $L$.

Why does this help us solve the original function $f(S)$? We can chain the sandwich inequalities to derive a data-dependent approximation guarantee. Let $S^*$ be the true, unknown optimal set that maximizes $f(S)$. We can reason about the quality of our greedy solution $S_L$ through the following steps:

  1. By the lower bound property: $f(S_L) \ge L(S_L)$
  2. By the greedy guarantee on submodular functions: $L(S_L) \ge (1 - 1/e) L(S^*)$
  3. By the upper bound property: $L(S^*) \ge \frac{L(S^*)}{U(S^*)} U(S^*) \ge \frac{L(S^*)}{U(S^*)} f(S^*)$

Combining these gives:

$$f(S_L) \ge (1 - 1/e) \cdot \frac{L(S^*)}{U(S^*)} \cdot f(S^*)$$

While we do not know $S^*$, we can bound the ratio $\frac{L(S^*)}{U(S^*)}$ empirically using the minimum ratio over all valid sets, or by evaluating the bounds on our selected sets. This framework allows practitioners to transform a theoretically hopeless non-submodular problem into one with provable, data-dependent performance guarantees.

Applications in Network Dynamics

The sandwich approximation strategy has become a foundational tool for managing complex, non-submodular interactions in social networks, where competing forces or threshold behaviors disrupt diminishing returns.

Misinformation and Influence Control

When defending a network against malicious information, the objective is often to minimize the final number of infected nodes by strategically blocking a subset of nodes. Jinghao Wang et al. demonstrate in Efficient Influence Minimization via Node Blocking that this minimization objective lacks submodularity. By bounding the objective between two monotonic submodular functions, the authors derive data-dependent approximation guarantees that enable efficient greedy node-blocking strategies.

Similarly, Guangmo Tong et al. tackle competing cascades in On Misinformation Containment in Online Social Networks. They bound the non-submodular containment objective between optimistic and pessimistic submodular scenarios, allowing a greedy algorithm to find high-quality solutions with provable performance guarantees.

Complementarity and Boosting

In viral marketing, products often exhibit synergy (e.g., buying a phone increases the likelihood of buying a compatible smart watch). Wei Lu et al. model this spectrum from competition to synergy in From Competition to Complementarity: Comparative Influence Diffusion and Maximization. When synergy destroys submodularity, the authors maintain computational tractability by sandwiching the influence function between simpler submodular proxies.

A related challenge is the $k$-boosting problem, where instead of selecting initial seed nodes, a marketer incentivizes existing users to become more susceptible to their friends' influence. Wei Chen et al. show in Boosting Information Spread: An Algorithmic Approach that this formulation introduces supermodular compounding effects. They resolve this by sandwiching the objective between submodular lower and upper bounds, providing a scalable, greedy-driven marketing strategy.

Complex Marketing Objectives

Modern optimization problems often incorporate nuanced goals beyond raw reach, which frequently breaks submodularity:

Surrogate and Proxy Functions

A closely related variant of the sandwich strategy involves identifying a single, highly accurate submodular surrogate function to act as a proxy for the non-submodular objective, rather than optimizing both bounds simultaneously.

For instance, when modeling networks containing "nearly" submodular nodes, Qiang Li et al. introduce the concept of $\epsilon$-almost submodularity in Influence Maximization with ε-Almost Submodular Threshold Functions. They show that replacing these non-submodular threshold functions with their closest submodular lower bounds allows standard greedy selection to maintain provable performance guarantees.

In competitive market environments where a new product aims to maximize its popularity ratio against an established incumbent, the direct objective function is inherently non-submodular. To solve this, Hao Liao et al. introduce a round-weighted surrogate function in Popularity Ratio Maximization: Surpassing Competitors through Influence Propagation. This surrogate is submodular, enabling efficient greedy optimization that remains within a narrow, provable margin of the true objective.

This surrogate mechanism also extends to continuous domains and sustainability problems. Andreas Krause et al. demonstrate in Sequential Decision Making in Computational Sustainability via Adaptive Submodularity how non-submodular objectives focused on uncertainty reduction can be mapped into an adaptive submodular framework using surrogate objectives, turning computationally impossible conservation and resource allocation problems into tasks that can be solved efficiently.

Continuous and Structural Extensions

The core philosophy of the sandwich framework—leveraging structured, tractable bounds to optimize complex landscapes—applies to continuous optimization and cost-minimization problems as well.

Continuous Submodular + Concave Optimization

In the continuous domain, Diminishing Returns (DR)-submodularity serves as the analog to discrete submodularity. Moran Feldman et al. study objectives that combine a continuous DR-submodular function and a concave function in Submodular + Concave. While the combined objective is neither purely submodular nor purely concave, the authors adapt the Frank-Wolfe framework to iteratively solve linear subproblems over convex constraints, providing strong theoretical approximation guarantees.

For continuous influence landscapes where marketing budgets must be saved, Wei Chen et al. introduce a tight concave upper bound based on coverage functions in Gradient Method for Continuous Influence Maximization with Budget-Saving Considerations. This upper bound simplifies the optimization landscape, allowing gradient-based methods to achieve significantly higher approximation ratios and faster execution times than general-purpose solvers.

Cost Minimization and Supermodular Bounds

The framework can also be inverted for cost-minimization problems. When an objective function lacks both submodularity and supermodularity, a substitute supermodular function can be constructed to serve as a provable upper bound. Tao Wu et al. apply this inverse bounding strategy in Joint Edge Aggregation and Association for Cost-Efficient Multi-Cell Federated Learning. By minimizing a supermodular upper-bound surrogate, the authors find tractable, high-quality solutions for otherwise NP-hard energy and communication cost-minimization problems at the network edge.

Key Foundational Work

On joint routing and server selection for MD video streaming in ad hoc networks (2007) — contributed 1 concept elements to this direction.
Sequential Decision Making in Computational Sustainability via Adaptive Submodularity (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_sandwich_approximation_framework_abdc0132,
  title = {sandwich approximation framework},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sandwich-approximation-framework/rdr_abdc013211294907bb67288281855af0},
  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_sandwich_approximation_framework_abdc0132_v1,
  title = {sandwich approximation framework},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sandwich-approximation-framework/rdr_abdc013211294907bb67288281855af0/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