{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T21:11:23Z","timestamp":1694639483500},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,4,16]],"date-time":"2010-04-16T00:00:00Z","timestamp":1271376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,1]]},"DOI":"10.1007\/s00453-010-9407-z","type":"journal-article","created":{"date-parts":[[2010,4,15]],"date-time":"2010-04-15T18:47:39Z","timestamp":1271357259000},"page":"94-114","source":"Crossref","is-referenced-by-count":6,"title":["Energy Efficient Monitoring in Sensor Networks"],"prefix":"10.1007","volume":"59","author":[{"given":"Amol","family":"Deshpande","sequence":"first","affiliation":[]},{"given":"Samir","family":"Khuller","sequence":"additional","affiliation":[]},{"given":"Azarakhsh","family":"Malekian","sequence":"additional","affiliation":[]},{"given":"Mohammed","family":"Toossi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,4,16]]},"reference":[{"key":"9407_CR1","doi-asserted-by":"crossref","unstructured":"Abrams, Z., Goel, A., Plotkin, S.: Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. In: IPSN \u201904: Proceedings of the Third International Symposium on Information Processing in Sensor Networks, pp.\u00a0424\u2013432 (2004)","DOI":"10.1145\/984622.984684"},{"key":"9407_CR2","doi-asserted-by":"crossref","unstructured":"Akyildiz, I.F., Su, W., Sankarasubramaniam, Y., Cayirci, E.: Wireless sensor networks: a survey. Comput. Netw. 38 (2002)","DOI":"10.1016\/S1389-1286(01)00302-4"},{"issue":"6","key":"9407_CR3","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/S0020-0190(02)00446-5","volume":"85","author":"N. Alon","year":"2003","unstructured":"Alon, N.: A simple algorithm for edge-coloring bipartite multigraphs. Inf. Process. Lett. 85(6), 301\u2013302 (2003)","journal-title":"Inf. Process. Lett."},{"key":"9407_CR4","doi-asserted-by":"crossref","unstructured":"Aloupis, G., Cardinal, J., Collette, S., Langerman, S., Smorodinsky, S.: Coloring geometric range spaces. In: Proceedings of the 8th Latin American Theoretical Informatics (LATIN\u201908) (2008)","DOI":"10.1007\/978-3-540-78773-0_13"},{"key":"9407_CR5","doi-asserted-by":"crossref","unstructured":"Benini, L., Castelli, G., Macii, A., Macii, E., Poncino, M., Scarsi, R.: A discrete-time battery model for high-level power estimation. In: DATE \u201900: Proceedings of the Conference on Design, Automation and Test in Europe, New York, NY, USA, pp.\u00a035\u201341 (2000)","DOI":"10.1145\/343647.343694"},{"key":"9407_CR6","unstructured":"Buchsbaum, A.L., Efrat, A., Jain, S., Venkatasubramanian, S., Yi, K.: Restricted strip covering and the sensor cover problem. In: SODA \u201907 (2007)"},{"key":"9407_CR7","doi-asserted-by":"crossref","unstructured":"Cardei, M., Wu, J.: Energy-efficient coverage problems in wireless ad-hoc sensor networks. Comput. Commun. 413\u2013420 (2006)","DOI":"10.1016\/j.comcom.2004.12.025"},{"key":"9407_CR8","doi-asserted-by":"crossref","unstructured":"Cardei, M., Thai, M.T., Li, Y., Wu, W.: Energy-efficient target coverage in wireless sensor networks. In: IEEE Infocom (2005)","DOI":"10.1109\/INFCOM.2005.1498475"},{"key":"9407_CR9","doi-asserted-by":"crossref","unstructured":"Cerpa, A., Elson, J., Estrin, D., Girod, L., Hamilton, M., Zhao, J.: Habitat monitoring: application driver for wireless communications technology. In: Proceedings of ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean (2001)","DOI":"10.1145\/371626.371720"},{"key":"9407_CR10","doi-asserted-by":"crossref","unstructured":"Deshpande, A., Khuller, S., Malekian, A., Toossi, M.: Energy efficient monitoring in sensor networks. In: LATIN 2008: Theoretical Informatics, 8th Latin American Symposium, B\u00fazios, Brazil, April 7\u201311, 2008, Proceedings, pp.\u00a0436\u2013448 (2008)","DOI":"10.1007\/978-3-540-78773-0_38"},{"key":"9407_CR11","doi-asserted-by":"crossref","unstructured":"Feige, U.: On maximizing welfare when utility functions are subadditive. In: STOC (2006)","DOI":"10.1145\/1132516.1132523"},{"key":"9407_CR12","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1137\/S0097539700380754","volume":"32","author":"U. Feige","year":"2002","unstructured":"Feige, U., Halldorsson, M., Kortsarz, G., Srinivasan, A.: Approximating the domatic number. SIAM J. Comput. 32, 172\u2013195 (2002)","journal-title":"SIAM J. Comput."},{"key":"9407_CR13","doi-asserted-by":"crossref","unstructured":"Frieze, A.M., Jerrum, M.: Improved approximation algorithms for max k-cut and max bisection. In: Proceedings of the 4th International IPCO Conference, pp.\u00a01\u201313 (1995)","DOI":"10.1007\/3-540-59408-6_37"},{"key":"9407_CR14","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/195058.195216","volume-title":"STOC \u201994: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing","author":"M.X. Goemans","year":"1994","unstructured":"Goemans, M.X., Williamson, D.P.: 879-approximation algorithms for max cut and max 2sat. In: STOC \u201994: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, New York, NY, USA, pp. 422\u2013431. ACM Press, New York (1994)"},{"key":"9407_CR15","first-page":"798","volume":"48","author":"J. Hastad","year":"2001","unstructured":"Hastad, J.: Some optimal inapproximability results. J.\u00a0ACM 48, 798\u2013859 (2001)","journal-title":"J.\u00a0ACM"},{"key":"9407_CR16","doi-asserted-by":"crossref","unstructured":"Hill, J., Szewczyk, R., Woo, A., Hollar, S., Cullerand, D., Pister, K.: System architecture directions for networked sensors. In: Proceedings of ASPLOS (November 2000)","DOI":"10.1145\/378993.379006"},{"key":"9407_CR17","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1145\/984622.984685","volume-title":"IPSN \u201904: Proceedings of the Third International Symposium on Information Processing in Sensor Networks","author":"C. Hsin","year":"2004","unstructured":"Hsin, C., Liu, M.: Network coverage using low duty-cycled sensors: random & coordinated sleep algorithms. In: IPSN \u201904: Proceedings of the Third International Symposium on Information Processing in Sensor Networks, New York, NY, USA, pp. 433\u2013442. ACM Press, New York (2004)"},{"key":"9407_CR18","doi-asserted-by":"crossref","unstructured":"Intanagonwiwat, C., Govindan, R., Estrin, D.: Directed diffusion: a\u00a0scalable and robust communication paradigm for sensor networks. In: Proceedings of ACM MOBICOM, Boston, MA (August 2000)","DOI":"10.1145\/345910.345920"},{"key":"9407_CR19","doi-asserted-by":"crossref","unstructured":"Juang, P., Oki, H., Wang, Y., Martonosi, M., Pehand, L., Rubenstein, D.: Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet. In: Proceedings of ASPLOS (October 2002)","DOI":"10.1145\/605397.605408"},{"key":"9407_CR20","unstructured":"Kahn, J.M., Katz, R.H., Pister, K.S.J.: Mobile networking for smart dust. In: ACM MOBICOM, Seattle, WA (August 1999)"},{"key":"9407_CR21","first-page":"172","volume":"15","author":"H. Liu","year":"2007","unstructured":"Liu, H., Jia, X., Wan, P., Yi, C., Makki, S., Pissinou, N.: Maximizing lifetime of sensor surveillance systems. IEEE\/ACM Trans. Netw. 15, 172\u2013195 (2007)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"9407_CR22","unstructured":"Lu, G., Sadagopan, N., Krishnamachari, B., Goel, A.: Delay efficient sleep scheduling in wireless sensor networks. In: IEEE Infocom (2005)"},{"key":"9407_CR23","doi-asserted-by":"crossref","unstructured":"Madden, S., Franklin, M.J., Hellerstein, J.M., Hong, W.: TAG: A Tiny AGgregation service for ad-hoc sensor networks. In: Proceedings of USENIX OSDI (2002)","DOI":"10.1145\/1060289.1060303"},{"key":"9407_CR24","doi-asserted-by":"crossref","unstructured":"Mainwaring, A., Polastre, J., Szewczyk, R., Culler, D.: Wireless sensor networks for habitat monitoring. In: ACM Workshop on Sensor Networks and Applications (2002)","DOI":"10.1145\/570738.570751"},{"key":"9407_CR25","doi-asserted-by":"crossref","unstructured":"Slijepcevic, S., Potkonjak, M.: Power efficient organization of wireless sensor networks. In: IEEE International Conference on Communications (ICC\u201901) (2001)","DOI":"10.1109\/ICC.2001.936985"},{"key":"9407_CR26","doi-asserted-by":"crossref","unstructured":"Vondrak, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: STOC (2008)","DOI":"10.1145\/1374376.1374389"},{"key":"9407_CR27","doi-asserted-by":"crossref","unstructured":"Wang, X., Xing, G., Zhang, Y., Lu, C., Pless, R., Gill, C.: Integrated coverage and connectivity configuration in wireless sensor networks. In: SenSys \u201903: Proceedings of the 1st International Conference on Embedded networked Sensor Systems, pp.\u00a028\u201339 (2003)","DOI":"10.1145\/958491.958496"},{"key":"9407_CR28","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1145\/800133.804355","volume-title":"STOC \u201978: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing","author":"M. Yannakakis","year":"1978","unstructured":"Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: STOC \u201978: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, New York, NY, USA, pp. 253\u2013264. ACM Press, New York (1978)"},{"key":"9407_CR29","unstructured":"Yao, Y., Gehrke, J.: Query processing in sensor networks. In: Proceedings of Conference on Innovative Data Systems Research (CIDR) (2003)"},{"key":"9407_CR30","unstructured":"Zhou, Z., Das, S., Gupta, H.: Connected k-coverage problem in sensor networks. In: Intl. Conference on Computer Communications and Networks (ICCCN) (2004)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9407-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9407-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9407-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,26]],"date-time":"2021-10-26T04:36:14Z","timestamp":1635222974000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9407-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,16]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["9407"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9407-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4,16]]}}}