Submodularity in the Wild: Sensors, Influence, and Summaries

The previous lesson gave a powerful hammer: any monotone submodular objective with a size budget is solved near-optimally by greedy. The skill that makes it useful is recognizing when a real problem is that nail.

The recipe is always the same three steps. Identify the ground set, the pool of items you choose from. Define the objective f(S), the value of a chosen subset. Then verify two things: that f is monotone, more is never worse, and that it is submodular, each item's marginal gain diminishes as the set grows.

Once those hold, you inherit the greedy algorithm and its (1 - 1/e) guarantee for free, with no problem-specific analysis. This lesson does that reduction for three flagship applications. The pattern to watch is how differently the objectives are described, and how identically they behave once the two properties are checked.

The first flagship application is deciding where to place a limited number of sensors, studied by Andreas Krause, Ajit Singh, and Carlos Guestrin in their 2008 paper "Near-Optimal Sensor Placements in Gaussian Processes".

The ground set is all candidate locations; you may install at most k sensors. The objective is how much they tell you about the quantity you are monitoring, temperature across a building, contamination across a water network. Krause and colleagues measured this as information gain: how much observing the chosen locations reduces uncertainty everywhere else, using the Gaussian-process models from the Bayesian-optimization path.

This objective is monotone, since more sensors never increase uncertainty, and submodular, since a new sensor in an already well-observed region tells you little that the others did not. So greedy applies, placing the sensor that most reduces remaining uncertainty each step, and comes within 63% of the unattainable optimal placement, usually much closer.

The second is viral marketing: choose k people in a social network to give a free product, so that word of mouth spreads it to as many others as possible. David Kempe, Jon Kleinberg, and Eva Tardos formalized it in their 2003 paper "Maximizing the Spread of Influence through a Social Network".

The ground set is the network's users; you pick k initial seeds. Influence spreads by a probabilistic model: in the independent cascade model, each newly activated person tries once to activate each neighbour, succeeding with some probability. The objective f(S) is the expected number of people eventually activated by seed set S.

Their key theorem is that this expected spread is monotone and submodular. Submodularity is intuitive: a new seed reaches fewer fresh people once your other seeds already blanket that part of the network. So greedy again gives a (1 - 1/e) approximation, and this paper opened an entire research area on influence in networks.

Influence maximization adds a wrinkle worth seeing, because it recurs across applications. The objective, expected spread, cannot be computed exactly; counting expected activations over all random cascades is itself hard.

So greedy is run with an estimated objective: simulate the cascade many times and average to estimate each marginal gain. This introduces small errors, and the guarantee softens to (1 - 1/e - epsilon), where epsilon reflects the estimation noise and shrinks as you run more simulations. The structural result survives approximate evaluation.

Here the lazy greedy method from the previous lesson becomes essential rather than merely nice. Estimating one marginal gain means running many simulations, so recomputing every item's gain each round would be crushing. The CELF algorithm of Leskovec and colleagues was introduced in exactly this networks setting, and made greedy influence maximization tractable on large graphs.

The third application is extractive summarization: choose a few sentences from a long document, or a few documents from a large set, that best represent the whole under a length budget. Hui Lin and Jeff Bilmes framed this submodularly in their 2011 paper "A Class of Submodular Functions for Document Summarization".

The ground set is the sentences; the budget is a length limit. A good summary needs two things at once, and both are submodular. Coverage rewards representing the document's content, and is submodular because once a topic is covered, another sentence on it adds little. Diversity rewards spreading across topics rather than piling onto one, and is naturally submodular because it penalizes redundancy directly.

Lin and Bilmes combined coverage and diversity into a single monotone submodular objective, so greedy produces a summary within the usual guarantee. The same template drives data summarization in machine learning: selecting a small, representative subset of a massive dataset to train on or inspect.

The three applications look unrelated: physical sensors, social contagion, text. Underneath they are one problem, which is the point of the whole framework.

Each has a ground set, a budget, and a monotone submodular objective, and each is therefore solved by the identical greedy algorithm with the identical guarantee. A practitioner who has implemented greedy once can attack all three, and dozens more: feature selection, active learning's choice of what to label, exemplar-based clustering, recommendation diversification. The framework's value is exactly this transfer. The hard, creative work is modelling a new problem as monotone submodular; the moment that is done, the algorithm and its proof come along at no extra cost.

A practical caution keeps this honest. Real objectives are sometimes only approximately submodular, obeying diminishing returns loosely rather than exactly.

This is common enough that theory addresses it. One tool is the submodularity ratio, a number measuring how far a function departs from true submodularity; greedy still carries a guarantee that degrades gracefully as that ratio worsens, rather than collapsing. Feature selection with correlated features is a typical case: not perfectly submodular, but close enough that greedy remains a strong, defensible default.

The lesson for practice is to check the two properties before quoting the guarantee. If monotonicity and submodularity hold exactly, greedy comes with its proof. If they hold approximately, greedy is still usually an excellent heuristic, but the clean 63% number no longer applies unchanged. Knowing which situation you are in is the difference between a guarantee and a hope.

Three applications from three different worlds, sensing, social networks, and language, turned out to be the same monotone submodular maximization, solved by the same greedy algorithm with the same guarantee. That recurrence is why submodularity is a standard part of the machine-learning toolkit rather than a niche result, and much of that standing traces to work by Krause and collaborators making the theory practical.

Everything so far has stayed inside the friendly case: monotone objective, simple size budget. That already covers a striking amount of ground, but not everything. Some objectives are non-monotone, where an item can hurt, and some constraints are richer than a size limit, such as choosing at most one item per category, or respecting a total cost.

The final lesson maps that wider territory: submodular minimization, non-monotone maximization, and constraints beyond cardinality, so you know what to reach for when the friendly case does not apply.