In the world of combinatorial optimization, the "greedy" approach is famously effective. To maximize a function, you simply pick the best available item, then the next best, and so on. For a broad class of problems known as submodular maximization—which models "diminishing returns" in everything from social network influence to sensor placement—mathematical theory provides a comforting safety net: the greedy algorithm is guaranteed to capture at least $1 - 1/e$ (roughly 63%) of the optimal value.
However, researchers have long noticed a puzzling discrepancy. While the 63% bound is mathematically "tight" (meaning there are adversarial cases where you can't do better), it is wildly pessimistic compared to real-world results. In practice, greedy algorithms don't just achieve 63%; they frequently capture 90%, 95%, or even 99% of the true optimum.
A growing body of research is dedicated to closing this "theory-practice gap," moving beyond worst-case analysis to explain why real-world data is so much easier to optimize than the math suggests.
The Empirical Reality of Near-Optimality
The first step in this research direction has been quantifying exactly how much performance we leave on the table. In TipTop: (Almost) Exact Solutions for Influence Maximization in Billion-scale Networks, Xiang Li and colleagues developed a way to find nearly exact solutions for massive networks. Their findings confirmed the suspicion: on real-world topologies like Twitter, greedy algorithms consistently achieve over 90% of the optimum, far outstripping their theoretical lower bounds.
This pattern repeats across different constraints and data types. Whether optimizing over a sliding window of data or handling distributed diversity maximization, researchers like Alessandro Epasto and Siddharth Gollapudi have shown that the adversarial conditions required to trigger the 63% worst-case scenario simply do not appear in natural datasets.
Quantifying the Shape of Functions
If the worst-case analysis is too broad, how do we create tighter, more realistic bounds? The answer lies in identifying structural properties of the objective functions that appear in practice.
One such property is curvature. In Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions, Rishabh K Iyer and Jeff Bilmes argue that the complexity of a submodular problem is determined by how far the function deviates from being a simple, additive (modular) sum. If a function has low curvature, it behaves more linearly, and greedy algorithms perform significantly better than the standard $1-1/e$ bound.
Another breakthrough concept is sharpness. Borrowed from continuous optimization, sharpness describes the "steepness" of the objective function around its maximum. In On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness, Sebastian Pokutta and his co-authors proved that the greedy algorithm automatically exploits this sharpness. It doesn't need to be told the function is "easy"; it naturally delivers tighter approximation guarantees by adapting to the local geometry of the problem.
From Global Bounds to Instance-Specific Proofs
While curvature and sharpness help explain the general success of greedy methods, they don't tell a practitioner how well the algorithm performed on one specific dataset. This has led to the development of instance-specific approximations.
In Instance Specific Approximations for Submodular Maximization, Eric Balkanski and Yaron Singer introduced DUAL, an algorithm that computes an upper bound on the optimum for a specific instance. By comparing the greedy result to this instance-specific bound, they were able to rigorously prove that greedy often captures over 95% of the available value on real-world datasets. This shifts the focus from "what is the worst possible performance?" to "how close are we to the best possible result right now?"
Stretching the Boundaries of Submodularity
The drive to explain practical success has also pushed researchers to look at functions that aren't strictly submodular but behave like they are. This is known as weak submodularity.
In fields like graph signal processing and neural network interpretability, the metrics we care about (like Mean Squared Error) often lack the formal "diminishing returns" property. Yet, as Ethan R. Elenberg and Alex Dimakis demonstrate with their STREAK algorithm, greedy-style algorithms still work remarkably well. By deriving new bounds based on the "submodularity ratio," researchers are beginning to provide a mathematical foundation for the "unreasonable effectiveness" of greedy selection in non-submodular domains.
Why It Matters
Understanding why these algorithms work is more than a theoretical exercise. As submodular optimization is applied to safety-critical systems or fairness-constrained selection, relying on a loose 63% guarantee is insufficient. By identifying the structural properties—like curvature, sharpness, and instance-specific bounds—that drive real-world performance, researchers are providing the tools necessary to deploy these efficient algorithms with much higher confidence in their near-optimality.