The problem of deploying sensors in a large water distribution network is considered, in order to detect the malicious introduction of contaminants. It is shown that a large class of realistic objective functions — such as reduction of detection time and the population protected from consuming contaminated water — exhibits an important diminishing returns effect called submodularity. The submodularity of these objectives is exploited in order to design efficient placement algorithms with provable performance guarantees. The algorithms presented in this paper do not rely on mixed integer programming, and scale well to networks of arbitrary size. The problem instances considered in the approach presented in this paper are orders of magnitude (a factor of 72) larger than the largest problems solved in the literature. It is shown how the method presented here can be extended to multicriteria optimization, selecting placements robust to sensor failures and optimizing minimax criteria. Extensive empirical evidence on the effectiveness of the method presented in this paper on two benchmark distribution networks, and an actual drinking water distribution system of greater than 21,000 nodes, is presented.

@article{krause08efficient,
	author = {Andreas Krause and Jure Leskovec and Carlos Guestrin and Jeanne VanBriesen and Christos Faloutsos},
	journal = {Journal of Water Resources Planning and Management},
	month = {November},
	number = {6},
	pages = {516-526},
	title = {Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks},
	volume = {134},
	year = {2008}}