networks
A hundred sensors for a city's water
It is 2006, and a consortium of cities has posed a grimly practical challenge: given a municipal water network of tens of thousands of junctions and the simulated spread of a contaminant from any of them, place a hundred sensors to catch outbreaks fast. The objective — expected detection benefit — again rewards diversity over redundancy: sensors that cover different failure scenarios beat sensors that all watch the same mains. Exploit that diminishing-returns structure for guarantees and for speed, because the naive greedy evaluation is itself too slow at this scale. Then report honestly what the hundred sensors cannot see. Get it wrong and the placements cluster where the model was certain, while the contamination enters through the neighborhood the simulation undersampled — discovered by emergency-room arrivals instead of instruments.
Who this problem belongs to
The two figures whose methods fit it best, out of 49 in contention.
This is Guestrin's own project, not an analogy. In the mid-2000s he led the Battle of the Water Sensor Networks work with Andreas Krause and Jure Leskovec, proving that outbreak-detection objectives like expected contamination coverage are submodular, that greedy placement is provably within a constant factor of optimal for such objectives, and that a lazy-evaluation trick (CELF) exploits diminishing returns to make greedy tractable on networks with tens of thousands of junctions where naive re-evaluation is far too slow. The paper reported exactly the honest failure mode the problem asks for: sensor sets that catch the modeled scenarios but miss contamination entering through undersampled parts of the network. Dropped into 2006, he is not applying a toolkit to this problem; he built the toolkit for this exact competition.
This is literally Leskovec's paper. The 2006 water-network challenge became cost-effective outbreak detection in networks, with Krause, Guestrin, Faloutsos, VanBriesen and Glance, on which he is first author: they unified contamination detection and blog-cascade monitoring under a single submodular objective, applied the greedy guarantee, and contributed CELF, the lazy-evaluation scheme that made naive greedy tractable at municipal scale, which is precisely the obstacle the problem names. The work also reported what the placements miss, including how sensitive the answer is to the simulated scenario set, the honest accounting demanded here. The underlying submodular-optimization theory he shares with Guestrin and Krause rather than owning, and the diminishing-returns guarantee is Nemhauser's. On this specific instance, though, he is the person who actually did it.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
49 figures are scored on this problem. Draw it in a battle to see where you land.