{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:35:37Z","timestamp":1774946137811,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,7,1]],"date-time":"2011-07-01T00:00:00Z","timestamp":1309478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0509383CNS-0625518IIS-0953413"],"award-info":[{"award-number":["CNS-0509383CNS-0625518IIS-0953413"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-08-1-0752"],"award-info":[{"award-number":["N00014-08-1-0752"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N000140911044"],"award-info":[{"award-number":["N000140911044"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["CNS-0509383CNS-0625518IIS-0953413"],"award-info":[{"award-number":["CNS-0509383CNS-0625518IIS-0953413"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF0710287"],"award-info":[{"award-number":["W911NF0710287"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2011,7]]},"abstract":"<jats:p>Where should we place sensors to efficiently monitor natural drinking water resources for contamination? Which blogs should we read to learn about the biggest stories on the Web? These problems share a fundamental challenge: How can we obtain the most useful information about the state of the world, at minimum cost?<\/jats:p>\n          <jats:p>Such information gathering, or active learning, problems are typically NP-hard, and were commonly addressed using heuristics without theoretical guarantees about the solution quality. In this article, we describe algorithms which efficiently find provably near-optimal solutions to large, complex information gathering problems. Our algorithms exploit submodularity, an intuitive notion of diminishing returns common to many sensing problems: the more sensors we have already deployed, the less we learn by placing another sensor. In addition to identifying the most informative sensing locations, our algorithms can handle more challenging settings, where sensors need to be able to reliably communicate over lossy links, where mobile robots are used for collecting data, or where solutions need to be robust against adversaries and sensor failures.<\/jats:p>\n          <jats:p>We also present results applying our algorithms to several real-world sensing tasks, including environmental monitoring using robotic sensors, activity recognition using a built sensing chair, a sensor placement challenge, and deciding which blogs to read on the Web.<\/jats:p>","DOI":"10.1145\/1989734.1989736","type":"journal-article","created":{"date-parts":[[2012,10,12]],"date-time":"2012-10-12T20:56:02Z","timestamp":1350075362000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":73,"title":["Submodularity and its applications in optimized information gathering"],"prefix":"10.1145","volume":"2","author":[{"given":"Andreas","family":"Krause","sequence":"first","affiliation":[{"name":"Swiss Federal Institute of Technology Zurich, Switzerland"}]},{"given":"Carlos","family":"Guestrin","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburg, PA"}]}],"member":"320","published-online":{"date-parts":[[2011,7,15]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 8th Annual Symposium on Water Distribution Systems Analysis.","author":"Berry J."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1365-2389.1981.tb01737.x"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS).","author":"Castro R."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177009939"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622737.1622744"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Cover T. M. and Thomas J. A. 1991. Elements of Information Theory. Wiley Interscience.   Cover T. M. and Thomas J. A. 1991. Elements of Information Theory. Wiley Interscience.","DOI":"10.1002\/0471200611"},{"key":"e_1_2_1_7_1","unstructured":"Cressie N. A. C. 1991. Statistics for Spatial Data. Wiley.  Cressie N. A. C. 1991. Statistics for Spatial Data. Wiley."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374384"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/0014013031000121977"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557056"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(78)91063-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1791212.1791239"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 23rd International Conference on Learning Theory.","author":"Golovin D."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/378583.378674"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/778415.778438"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1966.300074"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2007.893747"},{"key":"e_1_2_1_19_1","first-page":"22","article-title":"How many blogs does the world need","volume":"172","author":"Kinsley M.","year":"2008","journal-title":"Time Mag."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1756044"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI).","author":"Krause A."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273553"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2009.265"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1127777.1127782"},{"key":"e_1_2_1_25_1","first-page":"6","article-title":"Efficient sensor placement optimization for securing large water distribution networks","volume":"136","author":"Krause A.","year":"2008","journal-title":"J. Water Resources Plan. Manag."},{"key":"e_1_2_1_26_1","first-page":"2761","article-title":"Robust submodular observation selection","volume":"9","author":"Krause A.","year":"2008","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the International Conference on Information Processing in Sensor Networks.","author":"Krause A."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1001\/jama.1994.03520160070046"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728069"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Lovasz L. 1983. Submodular functions and convexity. Math. Program. State of the Art 235--257.  Lovasz L. 1983. Submodular functions and convexity. Math. Program. State of the Art 235--257.","DOI":"10.1007\/978-3-642-68874-4_10"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1992.4.4.590"},{"key":"e_1_2_1_33_1","unstructured":"MSNBC. 2007. China to spend &dollor;14.5 billion to clean up lake. http:\/\/www.msnbc.msn.com\/id\/21498294\/.  MSNBC. 2007. China to spend &dollor;14.5 billion to clean up lake. http:\/\/www.msnbc.msn.com\/id\/21498294\/."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294211.1294237"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Ostfeld A. Uber J. G. Salomons E. Berry J. W. Hart W. E. Phillips C. A. Watson J.-P. Dorini G. Jonkergouw P. Kapelan Z. di Pierro F. Khu S.-T. Savic D. Eliades D. Polycarpou M. Ghimire S. R. Barkdoll B. D. Gueli R. Huang J. J. McBean E. A. James W. Krause A. Leskovec J. Isovitsch S. Jianhua Guestrin C. VanBriesen J. Small M. Fischbeck P. Preis A. Propato M. Piller O. Trachtman G. B. Wu Z. Y. and Walski T. 2008. The battle of the water sensor networks (bwsn): A design challenge for engineers and algorithms. J. Water Resources Plann. Manag. (to appear).  Ostfeld A. Uber J. G. Salomons E. Berry J. W. Hart W. E. Phillips C. A. Watson J.-P. Dorini G. Jonkergouw P. Kapelan Z. di Pierro F. Khu S.-T. Savic D. Eliades D. Polycarpou M. Ghimire S. R. Barkdoll B. D. Gueli R. Huang J. J. McBean E. A. James W. Krause A. Leskovec J. Isovitsch S. Jianhua Guestrin C. VanBriesen J. Small M. Fischbeck P. Preis A. Propato M. Piller O. Trachtman G. B. Wu Z. Y. and Walski T. 2008. The battle of the water sensor networks (bwsn): A design challenge for engineers and algorithms. J. Water Resources Plann. Manag. (to appear).","DOI":"10.1061\/(ASCE)0733-9496(2008)134:6(556)"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1952-09620-8"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1061\/40430(1999)39"},{"key":"e_1_2_1_39_1","unstructured":"Schrijver A. 1998. Theory of Linear and Integer Programming. John Wiley & Sons.  Schrijver A. 1998. Theory of Linear and Integer Programming. John Wiley & Sons."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation (ICRA).","author":"Sim R."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622716.1622735"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).","author":"Singh A."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.5.1071"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.7326\/0003-4819-123-6-199509150-00008"},{"key":"e_1_2_1_45_1","unstructured":"Spinn3r. 2007. Rss content news feeds news content news crawler and web crawler apis. http:\/\/spinn3r.com\/.  Spinn3r. 2007. Rss content news feeds news content news crawler and web crawler apis. http:\/\/spinn3r.com\/."},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the RSS Conference.","author":"Stachniss C."},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the International Conference on Robotics and Automation.","author":"Stealey M. J."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 23rd Annual Conference on Neural Information Processing Systems (NIPS).","author":"Streeter M."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/3516.951364"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/env.701"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/79.985685"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the Workshop on Computer Vision and Pattern Recognition for Human Computer Interaction, (CVPR).","author":"Zhu M."}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1989734.1989736","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1989734.1989736","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:05:54Z","timestamp":1750244754000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1989734.1989736"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["10.1145\/1989734.1989736"],"URL":"https:\/\/doi.org\/10.1145\/1989734.1989736","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,7]]},"assertion":[{"value":"2010-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}