Greedy algorithms are among the simplest and most intuitive algorithms known to humans. Their name essentially gives their description: do the thing that looks best right now, and repeat until nothing looks good anymore or you’re forced to stop. Some of the best situations in computer science are also when greedy algorithms are optimal or near-optimal. There is a beautiful theory of this situation, known as the theory of matroids. We haven’t covered matroids on this blog (at some point we will), but in this post we will focus on the next best thing: when the greedy algorithm guarantees a reasonably good approximation to the optimal solution.
This situation isn’t hard to formalize, and we’ll make it as abstract as possible. Say you have a set of objects , and you’re looking to find the “best” subset . Here “best” is just measured by a fixed (known, efficiently computable) objective function . That is, accepts as input subsets of and outputs numbers so that better subsets have larger numbers. Then the goal is to find a subset maximizing .
In this generality the problem is clearly impossible. You’d have to check all subsets to be sure you didn’t miss the best one. So what conditions do we need on either or or both that makes this problem tractable? There are plenty you could try, but one very rich property is submodularity.
The Submodularity Condition
I think the simplest way to explain submodularity is in terms of coverage. Say you’re starting a new radio show and you have to choose which radio stations to broadcast from to reach the largest number of listeners. For simplicity say each radio station has one tower it broadcasts from, and you have a good estimate of the number of listeners you would reach if you broadcast from a given tower. For more simplicity, say it costs the same to broadcast from each tower, and your budget restricts you to a maximum of ten stations to broadcast from. So the question is: how do you pick towers to maximize your overall reach?
The hidden condition here is that some towers overlap in which listeners they reach. So if you broadcast from two towers in the same city, a listener who has access to both will just pick one or the other. In other words, there’s a diminished benefit to picking two overlapping towers if you already have chosen one.
This “diminishing returns” condition is a general idea you can impose on any function that takes in subsets of a given set and produces numbers. If is a set then for what seems like a strange reason we denote the set of all subsets of by . So we can state this condition more formally,
Definition: Let be a finite set. A function is called submodular if for all subsets and all ,
In other words, if measures “benefit,” then the marginal benefit of adding to is at least as high as the marginal benefit of adding it to . Since and are all arbitrary, this is as general as one could possibly make it.
Before we start doing things with submodular functions, let’s explore some basic properties. The first is an equivalent definition of submodularity
Proposition: is submodular if and only if for all , it holds that
Proof. If we assume has the condition from this proposition, then we can set , and the formula just works out. Conversely, if we have the condition from the definition, then using the fact that we can inductively apply the inequality to each element of to get
Next, we can tweak and combine submodular functions to get more submodular functions. In particular, non-negative linear combinations of sub-modular functions are submodular. In other words, if are submodular on the same set , and are all non-negative reals, then is also a submodular function on . It’s an easy exercise in applying the definition to see why this is true. This is important because when we’re designing objectives to maximize, we can design them by making some simple submodular pieces, and then picking an appropriate combination of those pieces.
The second property we need to impose on a submodular function is monotonicity. That is, as your sets get more elements added to them, their value under only goes up. In other words, is monotone when then . An interesting property of functions that are both submodular and monotone is that the truncation of such a function is also submodular and monotone. In other words, is still submodular when is monotone submodular and is a constant.
Submodularity and Monotonicity Give 1 – 1/e
The wonderful thing about submodular functions is that we have a lot of great algorithmic guarantees for working with them. We’ll prove right now that the coverage problem (while it might be hard to solve in general) can be approximated pretty well by the greedy algorithm.
Here’s the algorithmic setup. I give you a finite set and an efficient black-box to evaluate for any subset you want. I promise you that is monotone and submodular. Now I give you an integer between 1 and the size of , and your task is to quickly find a set of size for which is maximal among all subsets of size . That is, you design an algorithm that will work for any and runs in polynomial time in the sizes of .
In general this problem is NP-hard, meaning you’re not going to find a solution that works in the worst case (if you do, don’t call me; just claim your million dollar prize). So how well can we approximate the optimal value for by a different set of size ? The beauty is that, if your function is monotone and submodular, you can guarantee to get within 63% of the optimum. The hope (and reality) is that in practice it will often perform much better, but still this is pretty good! More formally,
Theorem: Let be a monotone, submodular, non-negative function on . The greedy algorithm, which starts with as the empty set and at every step picks an element which maximizes the marginal benefit , provides a set that achieves a -approximation of the optimum.
We’ll prove this in just a little bit more generality, and the generality is quite useful. If we call the sets chosen by the greedy algorithm (where now we might run the greedy algorithm for steps), then for all , we have
This allows us to run the algorithm for more than steps to get a better approximation by sets of larger size, and quantify how much better the guarantee on that approximation would be. It’s like an algorithmic way of hedging your risk. So let’s prove it.
Proof. Let’s set up some notation first. Fix your and , call the set chosen by the greedy algorithm at step , and call the optimal subset of size . Further call the value of the best set . Call the elements of (the order is irrelevant). Now for every monotonicity gives us . We can unravel this into a sum of marginal gains of adding single elements. The first step is
The second step removes , from the last term, the third removes , and so on until we have removed all of and get this sum
Now, applying submodularity, we can change all of these marginal benefits of “adding one more element to already with some stuff” to “adding one more element to just .” In symbols, the equation above is at most
and because is greedily chosen to maximize the benefit of adding a single element, so the above is at most
Chaining all of these together, we have . If we call , then this inequality can be rewritten as . Now by induction we can relate . Now use the fact that and the common inequality to get
And rearranging gives .
Setting gives the approximation bound we promised. But note that allowing the greedy algorithm to run longer can give much stronger guarantees, though it requires you to sacrifice the cardinality constraint. is about 63%, but doubling the size of gives about an 86% approximation guarantee. This is great for people in the real world, because you can quantify the gains you’d get by relaxing the constraints imposed on you (which are rarely set in stone).
So this is really great! We have quantifiable guarantees on a stupidly simple algorithm, and the setting is super general. And so if you have your problem and you manage to prove your function is submodular (this is often the hardest part), then you are likely to get this nice guarantee.
Extensions and Variations
This result on monotone submodular functions is just one part of a vast literature on finding approximation algorithms for submodular functions in various settings. In closing this post we’ll survey some of the highlights and provide references.
What we did in this post was maximize a monotone submodular function subject to a cardinality constraint . There are three basic variations we could do: we could drop constraints and see whether we can still get guarantees, we could look at minimization instead of maximization, and we could modify the kinds of constraints we impose on the solution.
There are a ton of different kinds of constraints, and we’ll discuss two. The first is where you need to get a certain value , and you want to find the smallest set that achieves this value. Laurence Wolsey (who proved a lot of these theorems) showed in 1982 that a slight variant of the greedy algorithm can achieve a set whose size is a multiplicative factor of worse than the optimum.
The second kind of constraint is a generalization of a cardinality constraint called a knapsack constraint. This means that each item has a cost, and you have a finite budget with which to spend on elements you add to . One might expect this natural extension of the greedy algorithm to work: pick the element which maximizes the ratio of increasing the value of to the cost (within your available budget). Unfortunately this algorithm can perform arbitrarily poorly, but there are two fun caveats. The first is that if you do both this augmented greedy algorithm and the greedy algorithm that ignores costs, then at least one of these can’t do too poorly. Specifically, one of them has to get at least a 30% approximation. This was shown by Leskovec et al in 2007. The second is that if you’re willing to spend more time in your greedy step by choosing the best subset of size 3, then you can get back to the approximation. This was shown by Sviridenko in 2004.
Now we could try dropping the monotonicity constraint. In this setting cardinality constraints are also superfluous, because it could be that the very large sets have low values. Now it turns out that if has no other restrictions (in particular, if it’s allowed to be negative), then even telling whether there’s a set with is NP-hard, but the optimum could be arbitrarily large and positive when it exists. But if you require that is non-negative, then you can get a 1/3-approximation, if you’re willing to add randomness you can get 2/5 in expectation, and with more subtle constraints you can get up to a 1/2 approximation. Anything better is NP-hard. Fiege, Mirrokni, and Vondrak have a nice FOCS paper on this.
Next, we could remove the monotonicity property and try to minimize the value of . It turns out that this problem always has an efficient solution, but the only algorithm I have heard of to solve it involves a very sophisticated technique called the ellipsoid algorithm. This is heavily related to linear programming and convex optimization, something which I hope to cover in more detail on this blog.
Finally, there are many interesting variations in the algorithmic procedure. For example, one could require that the elements are provided in some order (the streaming setting), and you have to pick at each step whether to put the element in your set or not. Alternatively, the objective functions might not be known ahead of time and you have to try to pick elements to jointly maximize them as they are revealed. These two settings have connections to bandit learning problems, which we’ve covered before on this blog. See this survey of Krause and Golovin for more on the connections, which also contains the main proof used in this post.
Indeed, despite the fact that many of the big results were proved in the 80′s, the analysis of submodular functions is still a big research topic. There was even a paper posted just the other day on the arXiv about it’s relation to ad serving! And wouldn’t you know, they proved a -approximation for their setting. There’s juts something about .
Until next time!