In discrete optimization, submodularity is the mathematical equivalent of the law of diminishing returns. It states that adding an element to a smaller set yields a greater marginal benefit than adding the same element to a larger set. When an objective function is submodular, a simple, short-sighted greedy algorithm is guaranteed to find a solution that is within a provable fraction (typically $1 - 1/e \approx 63\%$) of the absolute global optimum.
However, real-world systems rarely conform to such clean mathematical structures. When we optimize for net profit, build resilient networks, or design ecological corridors, the property of diminishing returns frequently collapses. Without submodularity, standard greedy algorithms lose their theoretical safety nets, risking catastrophic failures where local, incremental choices lead to highly suboptimal global outcomes.
To overcome this bottleneck, a growing body of research focuses on non-submodular optimization. By developing new mathematical relaxations, structural pruning techniques, and surrogate frameworks, researchers are finding ways to guarantee near-optimal solutions even when the comfort of diminishing returns is entirely absent.
Why Submodularity Breaks Down
To understand why submodularity fails, we must look at how competing objectives interact. Submodularity is fragile; simple arithmetic operations can instantly destroy it.
The Profit Dilemma: Subtracting Submodular Functions
Consider a social network provider trying to maximize viral marketing impact. The revenue generated from user engagement exhibits diminishing returns (submodularity). However, the hidden infrastructure cost of routing that data traffic also exhibits its own submodular structure due to economies of scale.
As Jing Tang et al. demonstrate in Towards Profit Maximization for Online Social Network Providers, when you subtract a submodular cost from a submodular revenue function to calculate net profit, the resulting objective function loses both submodularity and monotonicity.
[Submodular Revenue] - [Submodular Cost] = [Non-Submodular Net Profit]
(Diminishing Returns) (Diminishing Costs) (Unpredictable Fluctuations)
A similar breakdown occurs when balancing positive and negative word-of-mouth. As explored by Yipeng Chen et al. in Negative-Aware Influence Maximization on Social Networks and Ying Wang et al. in Opinion-aware Influence Maximization in Online Social Networks, subtracting the risk of spreading negative opinions from the benefit of positive reach destroys the submodular structure. The same mathematical hurdle appears when combining influence spread with cost-saving terms, as shown by Wei Chen 0013 et al. in Gradient Method for Continuous Influence Maximization with Budget-Saving Considerations, or when maximizing submodular objectives under submodular constraints, as analyzed by Madhavan R. Padmanabhan et al. in Maximizing submodular functions under submodular constraints.
The Corridor Effect: All-or-Nothing Rewards
In many spatial and network problems, an element has zero value until a complete sequence is formed. In Fast Combinatorial Algorithm for Optimizing the Spread of Cascades, XiaoJian Wu highlights this in the context of wildlife conservation. Protecting isolated parcels of land provides virtually no benefit to an endangered species; the value is only unlocked when the parcels connect to form a continuous migration corridor.
Because the marginal gain of the first few parcels is zero, a standard greedy algorithm will refuse to select them, failing to realize the massive long-term investment value. This all-or-nothing reward structure directly violates submodularity.
Mechanism 1: Quantifying the Deviation via Approximate Submodularity
If a function is not perfectly submodular, how close is it? One of the foundational insights of this field is that we can relax the strict definition of submodularity and measure the degree of violation using a metric known as the submodularity ratio.
In Greedy Sampling of Graph Signals, Alejandro Ribeiro et al. apply this concept to signal reconstruction on graphs. Common objectives like Mean Square Error do not naturally satisfy submodularity. However, by proving that these objectives satisfy approximate submodularity, the authors derive universal performance bounds showing that greedy algorithms can still yield near-optimal results, provided the deviation from diminishing returns remains bounded.
This strategy is mirrored in control theory. Luiz F. O. Chamon et al. extend this framing to actuator and sensor scheduling in Approximately Supermodular Scheduling Subject to Matroid Constraints. By mathematically bounding how far a linear-quadratic control objective strays from strict supermodularity, they provide practitioners with predictable performance guarantees, turning otherwise intractable control problems into computationally efficient tasks.
Mechanism 2: Structural Pruning and Search Space Reduction
When an objective function lacks submodularity, we cannot trust a simple step-by-step greedy path to find the global optimum. However, we can often exploit the underlying structural properties of the problem domain—such as graph topology—to aggressively prune the search space, making exact or highly accurate searches tractable.
[Full Search Space] ───► [Structural Pruning] ───► [Drastically Reduced Space]
(Intractable due to (Leverages graph layers (Solvable via optimized
non-submodularity) or upward routes) heuristics)
For instance, maximizing the core stability of a network by adding edges is highly non-submodular. To solve this, Zhongxin Zhou et al. introduce the EKC algorithm in K-Core Maximization: An Edge Addition Approach. Instead of evaluating all possible edge additions, the algorithm decomposes the graph into topological "onion layers," allowing it to prune irrelevant vertices and scale to massive datasets.
Similarly, in Enhance Stability of Network by Edge Anchor, Hongbo Qiu et al. tackle the non-submodular problem of anchoring relationships to boost network trussness. They design an "upward-route" pruning technique that bypasses the need for submodular guarantees by mathematically proving that large swaths of the network topology cannot contribute to the global optimum.
In the domain of social networks, the "Prune and Search" framework developed by Jing Tang et al. slashes the search space by up to 98%, demonstrating that structural insights can bypass the mathematical limitations of non-submodular objectives.
Mechanism 3: Continuous Relaxations and Surrogate Frameworks
Another powerful approach to bypassing non-submodularity is to transform the discrete, jagged optimization landscape into a smooth, continuous one where gradient-based methods can operate.
In Gradient Method for Continuous Influence Maximization with Budget-Saving Considerations, Wei Chen 0013 et al. address the loss of submodularity by integrating continuous gradient methods with Reverse Influence Sampling (RIS). By lifting the discrete problem into a continuous space, they achieve provable approximation guarantees and a 30x speedup over traditional stochastic approaches.
Alternatively, researchers use mathematical decompositions to isolate the problematic non-submodular components:
- Dual Decomposition: In natural language processing, integrating sentence compression into summarization systems disrupts submodularity. Miguel Almeida et al. bypass this in Fast and Robust Compressive Summarization with Dual Decomposition and Multi-Task Learning by using dual decomposition to split the problem into manageable sub-problems, avoiding the computational trap of traditional exact solvers.
- Lagrangian Relaxation: For spatial conservation cascades, XiaoJian Wu uses a primal-dual approach with Lagrangian relaxation to smooth out the all-or-nothing corridor constraints, delivering near-optimal results orders of magnitude faster than standard exact solvers.
Broad Applications Across Domains
The necessity of optimizing non-submodular functions spans a wide array of modern computational challenges:
- Network Resilience and Design: Evaluating network vulnerability via metrics like the forest index (Liwang Zhu et al.) or designing survivable topologies when physical infrastructure lacks sufficient redundancy (Michael Dinitz et al.) requires navigating non-submodular landscapes.
- Information Theory and Machine Learning: Even when information measures are derived from submodular functions, the resulting combinatorial measures do not always inherit submodularity without strict constraints, as shown by Rishabh K Iyer et al. in Submodular combinatorial information measures with applications in machine learning.
- Traffic Engineering: Selecting optimal intermediate routing nodes in networks is complicated because the total flow coverage objective lacks submodularity, requiring specialized algorithmic dichotomies (George Trimponias et al.).
- Evolutionary Dynamics: In Fixation Maximization in the Positional Moran Process, Joachim Brendborg et al. show that maximizing trait fixation in evolutionary models lacks submodularity for finite fitness advantages, requiring distinct approximation strategies for weak and strong selection regimes.
By moving beyond the restrictive assumption of diminishing returns, these diverse methodologies provide the mathematical and algorithmic tools necessary to solve complex, real-world optimization problems reliably and efficiently.
Key Foundational Work
Lagrangian Relaxation Techniques for Scalable Spatial Conservation Planning (2012) — contributed 2 concept elements to this direction.
Optimal Network Design for the Spread of Cascades (2010) — contributed 2 concept elements to this direction.