Submodular Maximization

In countless real-world scenarios, from designing a marketing campaign to building a machine learning model, the core challenge is one of selection: choosing the best combination of items from a vast pool of options. Brute-force approaches that check every possibility are computationally infeasible, a characteristic of so-called NP-hard problems. This raises a critical question: how can we make smart choices efficiently without getting lost in an ocean of complexity? The answer lies in a surprisingly common and intuitive property known as diminishing returns, which has a powerful mathematical counterpart called ​​submodularity​​. This article explores how this single principle provides the key to unlocking efficient and provably good solutions for a wide array of complex optimization problems.

First, in ​​Principles and Mechanisms​​, we will unpack the formal definition of submodularity, understand the "unreasonable effectiveness" of the simple greedy algorithm, and explore its limitations. Following that, in ​​Applications and Interdisciplinary Connections​​, we will journey through diverse fields—from artificial intelligence and social networks to ecology and experimental design—to witness how this fundamental concept is applied to solve tangible, important problems.

Imagine you're at an all-you-can-eat pizza buffet. That first slice is pure bliss. The second is still fantastic. By the time you're considering your eighth slice, however, the added satisfaction is considerably less than what you got from the first. This everyday experience is the heart of a profound mathematical concept known as ​​submodularity​​. It is, in essence, a formal name for the law of diminishing returns.

In many real-world selection problems, we are trying to choose a collection of items—a set—to maximize some notion of value or utility. We can describe this with a ​​set function​​, $f(S)$, which assigns a numerical score to any given set of items $S$.

A set function is said to be ​​submodular​​ if it exhibits this property of diminishing returns. More formally, the marginal gain of adding a new item, say $x$, to a set depends on what's already in the set. If we add $x$ to a small set $A$, the boost in value is greater than or equal to the boost we'd get from adding the very same item $x$ to a larger set $B$ that already contains $A$. Mathematically, for any sets $A \subseteq B$ and any item $x$ not in $B$:

This simple inequality is the secret ingredient behind the surprising effectiveness of many simple algorithms for complex optimization problems.

A classic example is the ​​Set Cover​​ problem. Imagine you are tasked with placing sensors to monitor events happening in a city. Each potential sensor location covers a specific subset of events. Your goal is to pick a limited number of sensor locations to cover the maximum number of unique events. The value function $f(S)$ is the total number of events covered by the set of sensors $S$.

This function is submodular. The first sensor you place might cover a huge number of previously unmonitored events. The second sensor will add to the coverage, but some of the events it monitors may already be covered by the first sensor; the new events it covers will be fewer. As you add more and more sensors, each new one tends to contribute less and less unique coverage, as the city becomes increasingly monitored. The marginal gain diminishes. This same principle applies whether we're covering events with sensors, features in a dataset with experiments, or vertices in a hypergraph with selected nodes.

Now, suppose you have $N$ possible sensor locations and a budget to place only $k$ of them. How do you choose the best set? Trying every possible combination of $k$ sensors out of $N$ is computationally disastrous. The number of combinations, $\binom{N}{k}$, grows explosively. For even moderate numbers like choosing 10 sensors from 100 locations, the number of possibilities is astronomical. This is a hallmark of an ​​NP-hard​​ problem—finding the absolute best solution is believed to be intractable for large instances.

Faced with this complexity, what's the most natural thing to do? Be greedy. At each step, simply choose the sensor that adds the most new coverage right now, without looking ahead. Start with an empty set, add the best single sensor. Then, given that choice, add the next-best sensor, and so on, until you've placed $k$ sensors. This is the ​​greedy algorithm​​.

It feels almost too simple to be effective. Surely this shortsighted strategy must often lead to globally poor decisions. But for monotone (adding items never hurts) submodular functions, a miracle occurs. A celebrated result from the 1970s shows that this simple greedy algorithm is guaranteed to find a solution that is at least $(1 - 1/e)$ times as good as the true, optimal solution. Here, $e$ is the base of the natural logarithm, so $(1 - 1/e)$ is approximately $0.632$. This means that by just making the locally best choice at each step, you are guaranteed to achieve at least 63.2% of the maximum possible value!

The intuition behind this remarkable guarantee is elegant. At any step, the total "potential" value remaining to be captured is the gap between your current solution and the optimal one. Because of submodularity, the sum of marginal gains of the items in the optimal solution is an upper bound on this gap. The greedy algorithm, by picking the single best item, is guaranteed to grab a sizable chunk (at least $1/k$ of the remaining potential) in each of its $k$ steps. This repeated "chipping away" at the gap leads mathematically to the $(1 - 1/e)$ floor. In return for a small, provable gap from optimality, you gain enormous speed. The greedy algorithm typically requires about $O(Nk)$ function evaluations, a dramatic improvement over the impossible-to-check $\binom{N}{k}$ combinations.

The $(1 - 1/e)$ guarantee is a beautiful result, but it hinges entirely on the submodular property. What happens if our value function exhibits the opposite behavior—​​synergy​​, where items are worth more together than they are apart? This property is sometimes called ​​supermodularity​​.

Consider a firm selecting a portfolio of R&D projects. Project A might be to develop a new battery, and Project B to develop a new electric motor. Each is valuable on its own. But together, they enable a revolutionary new electric vehicle, creating a value far greater than the sum of their parts. Here, the marginal gain of adding the motor project is larger if the battery project is already in the portfolio. Returns are increasing, not diminishing.

In such cases, the greedy algorithm can be catastrophically bad. Imagine the firm has a budget for just two projects. Another project, C, offers a solid, but not spectacular, standalone return. The greedy algorithm, looking for the biggest immediate gain, might pick Project C first. If C is expensive, it could exhaust the budget, preventing the selection of the A+B synergistic pair. As shown in scenarios like R&D selection or the Quadratic Knapsack Problem with positive synergies, by making a locally optimal first choice, the greedy algorithm can lock itself out of a globally brilliant solution. The ratio of the greedy solution's value to the optimal value can be driven arbitrarily close to zero. Submodularity isn't just a mathematical curiosity; it's the very foundation upon which the performance of the greedy algorithm rests.

Once you start looking for it, submodularity appears in the most surprising and diverse places, acting as a unifying principle.

• ​​Information and Machine Learning​​: How do you select a batch of experiments to run to learn a complex scientific model, like a potential energy surface in chemistry? The information you gain from a new experiment is submodular. A data point in a region you know little about is highly informative. An additional data point in a region you've already sampled heavily gives diminishing informational returns. This principle is formally captured in information-theoretic criteria like $F(S) = \frac{1}{2}\log\det(\mathbf{I} + \sigma^{-2}\mathbf{K}_{S})$, which is a cornerstone of Bayesian experimental design and is provably submodular.

• ​​Statistics and Model Building​​: In linear regression, a fundamental task is selecting a small subset of predictive features from a large pool. The common forward stepwise selection method is a greedy algorithm. The objective it tries to maximize, the coefficient of determination ($R^2$), is generally not submodular. However, when the predictors are uncorrelated, the function becomes perfectly additive (a special case of submodular), and the greedy algorithm is optimal. More importantly, when predictors have only small correlations, the function is ​​approximately submodular​​. This means the greedy approach, while not perfect, often performs well and comes with theoretical performance guarantees, explaining its enduring popularity.

• ​​Networks and Infrastructure​​: Consider a flow network, like a system of pipes or communication links. A fundamental concept is a ​​cut​​, which partitions the nodes of the network into two sets, say $S$ and its complement. The capacity of the cut, $c(S)$, is the total capacity of all edges going from $S$ to the complement. This cut-capacity function is submodular. This property is a key ingredient in proving structural theorems about networks, such as the existence of a compact representation of all minimum cuts called a Gomory-Hu tree. It also shows that submodularity is not just for maximization; it's a structural property that is equally crucial in minimization problems, though they require different algorithmic tools.

The world is not always as simple as "pick your favorite $k$ items." Our choices are often governed by more intricate rules and our objectives can be more nuanced. The theory of submodularity is rich enough to handle many of these complexities.

• ​​Elaborate Constraints: Matroids​​: Suppose you are choosing experiments, but some of them are mutually exclusive—for example, you can use lab A's spectrometer or lab B's, but not both. This type of constraint is known as a ​​partition matroid​​. The wonderful thing is that the greedy algorithm can be gracefully adapted. Instead of picking the element with the highest marginal gain overall, you simply pick the one with the highest gain among all feasible choices—those that don't violate your constraints. This ​​matroid-aware greedy algorithm​​ preserves strong approximation guarantees, far outperforming naive heuristics like "pick the best items first, then throw out conflicts". This reveals a deep and beautiful connection between submodularity and another elegant combinatorial structure, the matroid.

• ​​Negative Returns: Non-Monotonicity​​: So far, we've mostly assumed our functions are ​​monotone​​: adding an item never decreases the total value. But what if it can? Consider a function where choosing highly correlated items incurs a penalty. You might get a high score for item $\{a\}$ and item $\{b\}$ individually, but the combination $\{a, b\}$ gets a low score due to a large penalty term $w_{ab}$. This function might still be submodular (the marginal gain of adding a new item still diminishes), but it's not monotone. The simple greedy algorithm is ill-suited for this. A more sophisticated version, the ​​double-greedy algorithm​​, tackles this by simultaneously maintaining a set of items to keep and a set to discard. By making a balanced decision at each step, it can provide constant-factor approximation guarantees even for these challenging non-monotone objectives.

From choosing pizza slices to designing machine learning systems, from selecting R&D projects to analyzing vast networks, the principle of diminishing returns provides a powerful, unifying framework. Its mathematical embodiment, submodularity, gives us a license to use simple, intuitive greedy strategies and still expect remarkably good results, turning otherwise intractable problems into manageable ones. It is a testament to the power of finding the right abstraction for a complex world.

Previously, we established that a broad class of optimization problems governed by the simple and intuitive principle of diminishing returns can be solved with remarkable efficiency. For any system described by a monotone submodular function, a simple greedy algorithm—the strategy of always taking the next best step—is guaranteed to produce a result that is provably close to the best possible outcome.

This powerful mathematical result is not merely an abstraction; the principle of submodularity and its logic of diminishing returns appear in numerous real-world contexts. It provides a unifying structure for problems in fields from social networks and artificial intelligence to the very fabric of ecological systems. This section explores several key applications to witness this principle at work.

We live in an age of information overload. The central challenge is no longer access, but selection. Whether we are trying to build an AI that can read and summarize a document, or design a social media campaign that goes viral, the core task is to pick a small, potent subset from a vast sea of possibilities.

Imagine you are tasked with teaching a computer to write a summary of a long article. A naive approach might be to have the computer pick, one by one, the sentences that are most relevant to the overall document. This seems reasonable, but it often fails spectacularly. You might end up with five sentences that all say roughly the same thing, just phrased slightly differently. The summary is redundant and uninformative. The problem is that the value of a sentence is not absolute; it depends on what has already been said.

This is where diminishing returns come in. The first sentence on a new topic adds immense value. The second, a bit less. The third, even less. We can capture this by designing a scoring function that not only rewards relevance but also explicitly penalizes redundancy. For instance, we could define the value of a set of sentences $S$ as:

The penalty term, which grows with the overlap between selected sentences, ensures that the function is submodular. With this objective, the greedy strategy of picking the sentence with the highest marginal gain—the best combination of new relevance and low redundancy—now comes with our cherished $(1 - 1/e)$ performance guarantee. We have moved from a naive heuristic to an intelligent, provably effective strategy, simply by correctly modeling the submodular nature of the problem. This same principle is used in computer vision to select a diverse set of bounding boxes in object detection, avoiding redundant labels for the same object.

This idea extends beyond passive summarization to active influence. Consider the problem of "influence maximization" in a social network. You want to launch a new product and have a budget to give free samples to $k$ "influencers." Who do you choose to maximize the product's spread? You could give it to the $k$ people with the most followers. This is a static ranking strategy. But what if their audiences heavily overlap? A better strategy is to recognize that the number of people reached—the coverage—is a submodular function. The first influencer you pick might reach a million people. The second, chosen wisely, will reach a large number of new people, but the marginal gain will be less than the first, as some of their followers will have already been reached. An adaptive greedy algorithm, which at each step picks the person who covers the most not-yet-covered people, will vastly outperform a static ranking. It respects the diminishing returns of influence.

The logic of selection is not confined to the digital ether of bits and bytes. It extends to the concrete world of atoms and infrastructure. The problems of placing warehouses, cell towers, or data servers are often submodular in disguise.

Let's think about a Content Delivery Network (CDN), the system that allows you to stream a movie quickly no matter where you are. Companies must decide where to place their servers (caches) to minimize the time it takes for data to reach users. Let's say we have a budget to place $k=2$ caches in a network. Where should they go?

The goal is to minimize the average distance from a user to their nearest cache. This is equivalent to maximizing the reduction in average distance. Let’s call this reduction our "improvement" function. Is this function submodular? Absolutely. Imagine placing the first cache. It might drastically cut down travel times for a whole region, providing a huge improvement. Now, where do you place the second cache? If you place it near the first one, it will only offer a small additional improvement, helping a few users who were still a bit far from the first cache. Its marginal gain is small. If you place it in a completely different, unserved region, its marginal gain will be large, but likely not as large as the very first cache you placed in an entirely uncached network. The benefit of each new cache diminishes as the network becomes better served. This problem, a classic in operations research called the "facility location problem," is perfectly suited for our greedy approach.

Perhaps the most beautiful and surprising applications of submodularity are found not in systems we design, but in the natural world we seek to understand and preserve.

Ecologists face the heartbreakingly difficult task of designing nature reserves with limited budgets. Given a set of candidate land parcels, which ones should be protected to save the most species? The expected number of species you protect is a submodular function. This arises from a fundamental ecological observation known as the species-area relationship: the larger the habitat, the more species it can support, but at a decreasing rate. Adding a square kilometer of rainforest to a tiny reserve has a much bigger impact on species viability than adding it to a massive, continent-spanning park. We can model this with a concave function $g(x)$, where $x$ is the total area. The total value of a set of reserves $S$ is then a sum over all species, where each term is a composition of a concave function with the area of the reserves that contain that species. This structure, a sum of concave functions composed with modular ones, is guaranteed to be submodular.

It's not just about the size of the reserves, but also their connectivity. Animals need to move between them. A powerful way to model this is to define the value of a reserve network $S$ based on how well it connects the entire landscape. For each patch of land $u$ (both inside and outside the reserve), its connection benefit could be a function of its best link to the reserve network, i.e., $g(\max_{v \in S} w_{uv})$, where $w_{uv}$ is the connectivity from $u$ to $v$. Remarkably, this function is submodular for any non-decreasing function $g$. The reason is subtle and beautiful: the max operator itself imposes a diminishing returns structure. Once you have a great connection from $u$ to some reserve $v_1$, adding another reserve $v_2$ can only help if its connection is even better, and the marginal gain is only the difference between the new best and the old best.

This brings us to a profound point: information itself exhibits diminishing returns. This is the core idea behind the field of active learning or optimal experimental design. When scientists are trying to discover a new drug or map the properties of a new material, they can't perform every possible experiment. They must choose the most informative ones. In a Bayesian framework, we can model our ignorance with a probability distribution (like a Gaussian Process). The "informativeness" of a set of experiments can be measured by the mutual information they provide, or equivalently, by the volume of our prior uncertainty, often captured by the determinant of a kernel matrix, $|\mathbf{K}|$. Maximizing the log-determinant, $\log|\mathbf{K}_{\mathcal{B}}|$, a criterion known as D-optimality, turns out to be a submodular function maximization problem. The first experiment in a new domain tells us a huge amount. The tenth experiment nearby gives us just a little more precision. The greedy strategy of sequentially picking the experiment that resolves the most uncertainty is not just a heuristic; it's a provably near-optimal way to learn.

This principle is not just for AIs and ecologists; it applies to us, too. Think about how you might choose your courses for a semester. You have a limited amount of time and energy (a budget), and each course has a cost (e.g., credit hours). Each course covers a set of concepts. The first course you take on a topic, say introductory physics, gives you a massive amount of new knowledge. A second, more advanced course adds to that knowledge, but the gain is perhaps less than the first. A third course on the same topic offers even more specialized, but diminishing, returns. The total knowledge gained is a submodular function of the set of courses taken.

However, you can't just greedily pick the course that offers the most new knowledge. A 5-credit advanced seminar might offer more than a 3-credit introductory course, but is it worth the extra cost? For problems with budgets and costs—known as knapsack constraints—the greedy strategy must be slightly modified. Instead of picking the item with the highest marginal gain, we pick the one with the highest marginal gain per unit of cost. This "bang-for-your-buck" approach is the natural and provably effective greedy strategy for this more general, but equally common, type of submodular problem.

From summarizing text and caching videos to saving species and learning new subjects, the elegant logic of diminishing returns provides a unifying framework. It reminds us that in a world of finite resources, the secret to making wise choices is often to seek not just what is good, but what is new, and to understand that the value of anything is defined by the context of what we already have.