optimization
Where to place the sensors
It is the era of pervasive monitoring, and a hard combinatorial choice recurs everywhere: pick a handful of locations — sensors in a water network, monitors on a web of blogs, seeds in a social graph — to maximize coverage or influence, out of astronomically many subsets. Exhaustive search is hopeless. But the objective has a saving structure: diminishing returns, where each added element helps less than it would have earlier. Exploit this submodularity to prove that simple greedy selection — repeatedly adding whatever helps most — achieves a solution within a guaranteed constant factor of the unreachable optimum. Get it wrong and you brute-force a subset problem, or choose greedily with no guarantee — the submodular guarantee is why sensor placement and influence seeding are done well and fast.
Who this problem belongs to
The two figures whose methods fit it best, out of 71 in contention.
This is Guestrin's own theorem. With Andreas Krause he proved that sensor placement to maximize information or detect contamination is submodular, and that the greedy algorithm, despite exploring an astronomically large subset space, achieves a solution within a constant factor (1 - 1/e) of the unreachable optimum, published in the mid-2000s water-network and blog-monitoring papers that are now the canonical citation for this exact problem. His distributed systems work, GraphLab, exists precisely because these greedy submodular selections needed to scale past a single machine. No other carrier on this board owns both the theorem and its shipped implementation. He built the toolkit before the problem was even named a problem, and there is essentially no gap between his historical work and the scene described, which is why nothing here caps the score below the near-maximum.
This problem is, almost line for line, Leskovec's own paper: 'Cost-effective outbreak detection in networks,' first-authored with Krause, Guestrin, Faloutsos, VanBriesen and Glance at KDD 2007, which placed sensors in a municipal water distribution network and selected blogs to monitor for information cascades, using submodularity of the coverage objective to inherit the greedy constant-factor guarantee. The paper's CELF algorithm exploited submodularity a second time, lazily re-evaluating marginal gains so the greedy selection ran orders of magnitude faster on real networks. Both applications named in the problem statement, water networks and blogs, are literally his. He works downstream of the Nemhauser-Wolsey-Fisher guarantee rather than having proved it, and Kempe, Kleinberg and Tardos framed influence maximization submodularly first, which is all that keeps this short of the top.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
71 figures are scored on this problem. Draw it in a battle to see where you land.