Submodularity

How do we make the best choices when we can't just have a "little more" of something, but must instead select from a discrete collection of items? This question arises everywhere, from selecting a portfolio of stocks, to choosing features for a new product, to deciding which parcels of land to protect in a nature reserve. While we have an intuitive grasp of "diminishing returns" for continuous quantities—the fifth slice of pizza is less satisfying than the first—we lack a framework for this idea when dealing with sets. This knowledge gap makes it difficult to reason about and solve these complex selection problems.

This article introduces ​​submodularity​​, the powerful mathematical concept that fills this gap. Submodularity provides a formal language for diminishing returns in discrete optimization, unlocking solutions to problems once thought to be computationally intractable. By understanding this single principle, we gain insight into a vast range of phenomena. In the following sections, you will discover the core ideas behind this concept and its surprising reach. The section on "Principles and Mechanisms" will break down its formal definition and explore its presence in fundamental structures like graphs and networks. Subsequently, the section on "Applications and Interdisciplinary Connections" will reveal its remarkable effectiveness in solving real-world challenges across various scientific and technical domains, from machine learning to ecology.

Most of us have an intuitive grasp of the law of diminishing returns. The first slice of pizza after a long day is a transcendent experience. The second is great. By the fifth, you're just going through the motions. The "value" you get from each additional slice decreases. In the language of calculus, if we were to plot your "happiness" $H$ as a function of pizza slices $x$, the curve would be ​​concave​​—it would get less steep as you move to the right. The marginal gain, its slope or derivative $\frac{dH}{dx}$, is decreasing. As one of our ecological problems beautifully illustrates, the probability of a species' survival shows the same behavior with increasing habitat area: adding a square kilometer to a tiny reserve helps a lot, while adding it to a vast one helps only a little. This diminishing return is captured by the negative second derivative of the persistence probability with respect to area, $\frac{\partial^2 P}{\partial A^2} \lt 0$.

But what if our choices aren't continuous, like adding more pizza dough? What if we are choosing from a discrete collection of things? How do we select the best committee of people, the most effective locations for fire stations, or the most valuable set of features for a new product? We need a way to talk about "diminishing returns" for functions that operate on sets of items, not on a single continuous variable.

This is precisely what the concept of ​​submodularity​​ does. A function $f$ that assigns a value to every possible subset of a ground set $E$ is submodular if it satisfies the property of diminishing marginal returns. Formally, for any two sets $A$ and $B$ such that $A \subseteq B \subseteq E$, and any new element $x \notin B$, the gain of adding $x$ to the smaller set $A$ is at least as large as the gain of adding it to the larger set $B$:

$f(A \cup \{x\}) - f(A) \ge f(B \cup \{x\}) - f(B)$

This is the soul of submodularity. Adding a brilliant programmer to a two-person startup team might triple its productivity. Adding that same programmer to a 500-person division at a large corporation will have a much smaller relative impact. The "value" of the new element depends on the context it's being added to, and it's less when the context is already "rich."

There is an equivalent, more symmetric definition that you will often see in textbooks. For any two sets $A$ and $B$, a function $f$ is submodular if:

$f(A) + f(B) \ge f(A \cup B) + f(A \cap B)$

It might not be immediately obvious, but this inequality expresses the same core idea: the value is "concentrated" in the individual sets more than it is in their union and intersection. The whole is, in a sense, less than the sum of its parts, because of the redundancy or overlap in what $A$ and $B$ contribute.

One of the most natural places to find submodularity is in the structure of graphs. Imagine you are building a computer network by adding communication links (edges) between nodes (vertices). You want to connect as many nodes as possible, but you must avoid creating loops or cycles, as these can cause data packets to circulate endlessly.

Let's define a value function, $r(S)$, for any set of available edges $S$, as the maximum number of edges you can use from $S$ without creating a cycle. This is equivalent to finding the size of the largest "forest" (a collection of trees) within the subgraph formed by the edges in $S$.

Is this function submodular? Let's think about it. If you have a very sparse set of edges $A$, adding a new edge $x$ is very likely to connect previously disconnected parts of your network. The marginal gain in $r$ is 1. Now, imagine you have a much denser set of edges $B$ that already contains $A$. Adding that same edge $x$ is now much more likely to complete a cycle with edges already present in $B$. If it does, you can't add it to your forest, and the marginal gain is 0. The gain of adding $x$ to the smaller set $A$ was greater than or equal to the gain of adding it to the larger set $B$. This is exactly diminishing returns!

We can see this with a concrete example. Consider four computer terminals, $v_1, v_2, v_3, v_4$. Let's consider two possible sets of connections: $A = \{(v_1, v_2), (v_3, v_4)\}$ and $B = \{(v_1, v_3), (v_2, v_4)\}$.

• For set $A$, we have two separate links. Both can be used without creating a cycle. So, $r(A) = 2$.
• For set $B$, we also have two separate links. Both can be used. So, $r(B) = 2$.
• The intersection is empty, $A \cap B = \emptyset$, so its value is $r(A \cap B) = 0$.
• The union, $A \cup B$, contains all four edges, which form a square cycle $v_1-v_2-v_4-v_3-v_1$. To avoid a cycle, we can only use three of these four edges. So, $r(A \cup B) = 3$.

Now let's check the submodular inequality: $r(A) + r(B) = 2 + 2 = 4$ $r(A \cup B) + r(A \cap B) = 3 + 0 = 3$ Indeed, $4 \ge 3$. The inequality holds, as demonstrated in the specific calculation from problem on a cycle graph. This rank function of a ​​graphic matroid​​ is a canonical example of a submodular function. However, be careful not to assume that any intuitive counting function is submodular. For instance, a function counting the number of intersection points among a set of lines might seem similar, but it can violate related properties and fails to be a matroid rank function, demonstrating that these structural properties are quite specific.

Let's switch gears to a different kind of network: a transportation grid with a source $s$ and a sink $t$, like a system of pipes carrying water from a reservoir to a city. Each pipe (a directed edge) has a maximum capacity. A fundamental question is: what is the maximum rate at which water can be sent from $s$ to $t$?

The answer is limited by the "bottlenecks" in the system. We can formalize a bottleneck as an ​​s-t cut​​, which is a partition of all nodes (junctions) into two sets, a set $S$ containing the source $s$ and a set $\bar{S}$ containing the sink $t$. The ​​capacity of the cut​​ $c(S, \bar{S})$ is the total capacity of all pipes that go from a node in $S$ to a node in $\bar{S}$. It's the maximum flow that can pass through this particular partition of the network. The famous max-flow min-cut theorem states that the maximum flow through the whole network is equal to the capacity of the minimum possible cut.

What is fascinating is that this cut capacity function, $c(S, \bar{S})$, is also submodular! The set of nodes on the "source side" of the cut, $S$, is the variable. It's not at all obvious why this should be true. But this property has profound consequences.

Consider two minimum cuts, $(S_1, \bar{S}_1)$ and $(S_2, \bar{S}_2)$. Because the cut function is submodular, we know that $c(S_1) + c(S_2) \ge c(S_1 \cup S_2) + c(S_1 \cap S_2)$. Since $S_1$ and $S_2$ define minimum cuts, their capacity is the minimum possible, let's call it $C_{min}$. So, the left side of the inequality is $2C_{min}$. The capacity of any cut must be at least $C_{min}$, so the sum on the right side must be at least $2C_{min}$. The only way to satisfy both conditions is if equality holds and both the union cut $(S_1 \cup S_2, \overline{S_1 \cup S_2})$ and the intersection cut $(S_1 \cap S_2, \overline{S_1 \cap S_2})$ are also minimum cuts! This incredible result, which follows directly from submodularity, shows that the family of minimum cuts has a beautiful, tightly-knit lattice structure.

Perhaps the most intuitive family of submodular functions relates to the idea of ​​coverage​​. Imagine you're placing Wi-Fi routers in a building. The value of your set of routers is the total area they cover. The first router you place covers a large new area. The tenth router you place will likely cover an area that already has some signal, so its marginal contribution to the total covered area is smaller. This is a submodular process.

This principle appears in many critical real-world applications. A prime example is systematic conservation planning. Here, the goal is to select a set of land parcels $S$ to form a reserve network. The value of the network, $V(S)$, might be defined as the total representation of various conservation features (like species habitats or ecosystem types). For each feature $f$, there's a target $T_f$. The value contributed by feature $f$ is the amount of it protected by the reserves in $S$, but only up to the target $T_f$. The marginal gain of adding a new parcel $i$ to an existing reserve network $S$ is called its ​​complementarity​​. This gain is high if parcel $i$ contains features that are currently poorly represented in $S$. But if the features in parcel $i$ are already well-represented and their targets are nearly met, the marginal gain is low. This is a clear case of diminishing returns, and indeed, this value function $V(S)$ is submodular.

More complex versions of this idea exist. One might define the value of a reserve network $S$ by how well it connects to all other potential habitats in the landscape. A function like $f(S) = \sum_{u} p_u \max_{v \in S} w_{uv}$, which measures the connectivity from all sites $u$ to their best-connected point $v$ in the reserve set $S$, is also monotone and submodular.

So, we've found this property of diminishing returns in graphs, networks, and conservation plans. This might seem like a neat classification, but its true importance is computational. Submodularity is a secret weapon that makes hard problems easy.

Many of the problems we've discussed—choosing the best $k$ parcels for a reserve, the best $k$ edges for a network—are ​​NP-hard​​. This means that finding the absolute, provably optimal solution is computationally infeasible for anything but the smallest examples. The number of combinations to check explodes far too quickly.

This is where submodularity works its magic. If the value function $f(S)$ you are trying to maximize is monotone and submodular, then a breathtakingly simple ​​greedy algorithm​​ is provably effective. The algorithm is just what you'd think:

1. Start with an empty set.
2. At each step, find the one element that provides the largest marginal increase in value (the best "bang for your buck").
3. Add it to your set.
4. Repeat $k$ times.

In general, greedy algorithms can be terribly shortsighted and lead to poor outcomes. But for monotone submodular functions, a landmark result by Nemhauser, Wolsey, and Fisher in 1978 proved that this simple greedy approach is guaranteed to yield a solution that is at least $(1 - 1/e) \approx 63\%$ of the true optimal value. This approximation guarantee is a game-changer. It turns an intractable problem into a solvable one, providing a near-optimal solution quickly. The same greedy logic also provides constant-factor approximations for more complex constraints, like selecting at most one site from each administrative region.

To see why the submodular property is so essential, consider a case where it's absent. Imagine designing a power system where modules are only "stable" in specific combinations, for instance, modules $\{m_1, m_2\}$ are a stable pair and $\{m_3, m_4\}$ are another, but mixing them is forbidden. Let their power outputs (weights) be $w(m_1)=15, w(m_2)=4, w(m_3)=13, w(m_4)=13$. The value function here is not submodular. The greedy algorithm, seeking the highest power, would first choose $m_1$ (15 MW). This immediately prevents it from ever choosing $m_3$ or $m_4$. It then adds $m_2$ for a total of $19$ MW. However, the optimal solution was to ignore the tempting $m_1$ and choose the pair $\{m_3, m_4\}$, yielding $26$ MW. The greedy choice led to a significantly suboptimal outcome. This failure occurs precisely because the underlying value function lacks the well-behaved structure of diminishing returns.

Submodularity, therefore, is more than just a mathematical curiosity. It is a fundamental principle that describes a vast range of phenomena, and its presence is a powerful sign that simple, intuitive, and efficient strategies can succeed even in the face of overwhelming complexity.

Now that we have grappled with the mathematical soul of submodularity—this elegant principle of diminishing returns—we might be tempted to file it away in a cabinet labeled "abstract curiosities." But to do so would be a profound mistake. It would be like learning the rules of chess and never playing a game, or understanding the laws of harmony and never listening to a symphony. The true beauty and power of submodularity are not found in its definition, but in its omnipresence. This is not some esoteric concept confined to the blackboard; it is a fundamental pattern woven into the fabric of the natural world, social systems, and the very process of human discovery.

Let us embark on a journey to see where this idea lives. We will find that the simple, intuitive, and often-scorned "greedy" approach to problem-solving is not only frequently employed but, in the presence of submodularity, is endowed with a kind of unreasonable effectiveness.

Imagine you are at a pizza parlor with a budget for exactly three toppings. The first topping you choose—say, pepperoni—transforms a plain cheese pizza into something far more interesting. The second, perhaps mushrooms, adds a new dimension of flavor. But what about the third? Olives? By now, the pizza is already quite complex. The marginal improvement in your dining experience from that third topping is likely less than the improvement you got from the first. This is diminishing returns in its most delicious form.

This simple intuition is the key to solving a vast array of practical optimization problems. Consider the task of placing a limited number of sensors to monitor a large area, or selecting a few key individuals in a company to receive a critical piece of information. A more concrete version of this is the problem of maximizing network coverage: given a network of roads or computer connections, which $k$ nodes should you place resources at to "cover" the maximum number of connections?.

In all these cases, the value we get from a set of selected items—whether they are pizza toppings, sensors, or network nodes—is a submodular function. The set of edges covered by a set of vertices is a perfect example. Adding a new vertex to a small set of selected vertices will likely cover many new edges. Adding that same vertex to a large set that has already covered most of the network will yield a much smaller number of newly covered edges.

Because the underlying objective function is submodular, the greedy algorithm—at each step, picking the single best item that provides the largest marginal gain—is not just a lazy heuristic. It comes with a remarkable guarantee. As we saw in the previous section, this simple procedure is guaranteed to give a solution that is at least $(1 - 1/e)$, or about 63%, as good as the absolute best possible solution. In a world of NP-hard problems where finding the perfect answer is computationally impossible, a provable guarantee of "pretty good" is a triumph.

The true power of this idea shines when we move from these abstract examples to problems of profound real-world importance. Take systematic conservation planning. Ecologists face the agonizing task of deciding which parcels of land to protect to preserve biodiversity, often under a strict budget and in the face of a changing climate. What is the "value" of a set of nature reserves? It's not simply the sum of the species in each one. The real value lies in complementarity. A new reserve that protects species not found in any existing reserve is immensely valuable. A new reserve that largely duplicates species we have already protected is less so. This is, once again, the principle of diminishing returns. By carefully crafting a submodular objective function that rewards the representation of rare species within climate-stable refugia, conservationists can use this very same greedy logic to design reserve networks that are provably effective at safeguarding the maximum amount of our planet's natural heritage.

Submodularity doesn't just govern static selection problems; it also describes the dynamics of processes that unfold over time. Think about the spread of a new idea, a piece of news, or a virus through a social network. This is the domain of ​​influence maximization​​. If you want to market a new product and can only afford to give free samples to a few "influencers," who should you choose?

The expected number of people who will eventually adopt the product is a submodular function of the initial set of people you seed. Giving a sample to an influencer whose followers largely overlap with an influencer you have already chosen is a waste of resources. The marginal gain is small. The greedy strategy, therefore, is to iteratively pick the person who, given the seeds already selected, can reach the largest number of new people. Again, because of submodularity, this intuitive approach is provably near-optimal. The same logic that helps us pick pizza toppings helps us make ideas go viral.

This concept of information spread can be found in more surprising places. In the field of information theory, engineers design sophisticated error-correcting codes that allow us to communicate reliably over noisy channels, like from a deep-space probe back to Earth. Many of these systems use iterative decoders that pass information back and forth, refining their guess about the original message in each round. An ​​Extrinsic Information Transfer (EXIT) chart​​ is a tool used to visualize this process. It plots the "new" information a decoder can generate as a function of the "old" information it was given. A key feature of these charts is that the curve flattens out as the input information approaches perfection. This is a perfect graphical representation of diminishing returns: the more you already know, the harder it is to learn something new. The decoder's ability to gain information is a submodular process.

Perhaps the most exciting application of submodularity is in guiding the process of scientific discovery itself. Science is often a sequence of experiments, and experiments can be expensive. If you have a limited budget, which experiments should you run to learn the most about the universe?

This is the central question of ​​active learning​​ in machine learning. Imagine you are a computational chemist trying to map out the complex potential energy surface of a molecule, which determines its chemical properties. You can run very expensive quantum simulations, but only a few. Which molecular configurations should you simulate? You want to choose a set of configurations that, when simulated, will reduce your uncertainty about the entire surface as much as possible. The information gain—a concept from information theory quantified by the mutual information—turns out to be a submodular function of the set of experiments you choose. A greedy approach, where at each step you choose the single most informative experiment to run next, is a powerful and principled way to guide your research. Submodularity provides a framework for optimally interrogating the unknown.

We see the same pattern in computational biology when trying to solve the ​​protein inference​​ problem. After an experiment, biologists are often left with a soup of peptide fragments that could potentially map to thousands of different proteins. To resolve this ambiguity, they can run targeted assays. But which peptides should they target? The goal is to choose a small set of assays that resolves the most ambiguity. The expected number of proteins that can be uniquely identified is, you guessed it, a submodular function of the set of chosen assays.

The principle of diminishing returns is so fundamental that it can even explain patterns that have emerged over evolutionary timescales. In ​​evolutionary biology​​, theorists model the trade-offs organisms face. Consider parental investment. An offspring's chance of survival increases with the amount of care it receives from its parents. However, the benefit of each additional unit of care is not constant. The first few acts of feeding and protection dramatically increase survival odds, but beyond a certain point, more care yields smaller and smaller gains. This is modeled by a concave survival function, which is the continuous analogue of submodularity. This simple fact—that parental care has diminishing returns—has profound consequences, helping to determine which sex evolves to bear the primary costs of raising young.

Finally, submodularity is not just a tool for building applications; it is a deep structural concept in ​​theoretical computer science​​. We can use it to define generalized versions of classic hard problems. The famous Bin Packing problem asks how to fit items of different sizes into a fixed number of bins. The "Submodular Bin Packing" problem generalizes this by imagining that when items are placed together, they might share resources, so their combined "size" is a submodular function of the set. Standard bin packing is just the special case where this function is a simple sum. By studying these generalized problems, theorists gain a deeper understanding of the landscape of computational complexity.

From protecting endangered species to decoding messages from space, from making ideas go viral to shaping the course of evolution, the principle of submodularity is a unifying thread. It reminds us that in a complex world, the simple, greedy strategy of making the best local choice can often lead to surprisingly, and provably, good global outcomes. It is a testament to the fact that sometimes, the most intuitive ideas are also the most profound.