{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,9]],"date-time":"2025-02-09T05:17:11Z","timestamp":1739078231944,"version":"3.37.0"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540922940"},{"type":"electronic","value":"9783540922957"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-92295-7_5","type":"book-chapter","created":{"date-parts":[[2009,3,25]],"date-time":"2009-03-25T08:00:00Z","timestamp":1237968000000},"page":"11-24","source":"Crossref","is-referenced-by-count":8,"title":["Finding Facilities Fast"],"prefix":"10.1007","author":[{"given":"Saurav","family":"Pandit","sequence":"first","affiliation":[]},{"given":"Sriram V.","family":"Pemmaraju","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Heinzelman, W.R., Chandrakasan, A., Balakrishnan, H.: Energy-efficient communication protocol for wireless microsensor networks. In: HICSS 2000: Proceedings of the 33rd Hawaii International Conference on System Sciences, vol.\u00a08, p. 8020 (2000)","DOI":"10.1109\/HICSS.2000.926982"},{"issue":"5","key":"5_CR2","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/s11276-006-8150-5","volume":"13","author":"T. Wu","year":"2007","unstructured":"Wu, T., Biswas, S.: Minimizing inter-cluster interference by self-reorganizing mac allocation in sensor networks. Wireless Networks\u00a013(5), 691\u2013703 (2007)","journal-title":"Wireless Networks"},{"issue":"2","key":"5_CR3","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1023\/B:MONE.0000013625.87793.13","volume":"9","author":"P.J. Wan","year":"2004","unstructured":"Wan, P.J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. Mob. Netw. Appl.\u00a09(2), 141\u2013149 (2004)","journal-title":"Mob. Netw. Appl."},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"Wang, Y., Li, X.Y.: Localized construction of bounded degree and planar spanner for wireless ad hoc networks. In: DIALM-POMC 2003: Proceedings of the 2003 joint workshop on Foundations of mobile computing, pp. 59\u201368 (2003)","DOI":"10.1145\/941079.941088"},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"Wang, Y., Wang, W., Li, X.Y.: Distributed low-cost backbone formation for wireless ad hoc networks. In: MobiHoc., pp. 2\u201313 (2005)","DOI":"10.1145\/1062689.1062692"},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"Deb, B., Nath, B.: On the node-scheduling approach to topology control in ad hoc networks. In: MobiHoc 2005: Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, pp. 14\u201326 (2005)","DOI":"10.1145\/1062689.1062693"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Kang, J., Zhang, Y., Nath, B.: Analysis of resource increase and decrease algorithm in wireless sensor networks. In: ISCC 2006: Proceedings of the 11th IEEE Symposium on Computers and Communications, pp. 585\u2013590 (2006)","DOI":"10.1109\/ISCC.2006.37"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: STOC 2004: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 281\u2013290 (2004)","DOI":"10.1145\/1007352.1007399"},{"key":"5_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/11561071_42","volume-title":"Algorithms \u2013 ESA 2005","author":"V. Bil\u00f2","year":"2005","unstructured":"Bil\u00f2, V., Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Geometric clustering to minimize the sum of cluster sizes. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 460\u2013471. Springer, Heidelberg (2005)"},{"issue":"4","key":"5_CR10","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1002\/net.10097","volume":"42","author":"X. Cheng","year":"2003","unstructured":"Cheng, X., Huang, X., Li, D., Wu, W., Du, D.Z.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks\u00a042(4), 202\u2013208 (2003)","journal-title":"Networks"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"Amb\u00fchl, C., Erlebach, T., Mihal\u00e1k, M., Nunkesser, M.: Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In: APPROX-RANDOM, pp. 3\u201314 (2006)","DOI":"10.1007\/11830924_3"},{"key":"5_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/978-3-540-78773-0_64","volume-title":"LATIN 2008: Theoretical Informatics","author":"T. Erlebach","year":"2008","unstructured":"Erlebach, T., van Leeuwen, E.J.: Domination in geometric intersection graphs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol.\u00a04957, pp. 747\u2013758. Springer, Heidelberg (2008)"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Huang, Y., Gao, X., Zhang, Z., Wu, W.: A better constant-factor approximation for weighted dominating set in unit disk graph. Journal of Combinatorial Optimization (2008)","DOI":"10.1007\/s10878-008-9146-0"},{"issue":"2","key":"5_CR14","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K. Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM\u00a048(2), 274\u2013296 (2001)","journal-title":"J. ACM"},{"key":"5_CR15","volume-title":"Algorithms for Sensor and Ad Hoc Networks","author":"C. Frank","year":"2007","unstructured":"Frank, C.: Algorithms for Sensor and Ad Hoc Networks. Springer, Heidelberg (2007)"},{"issue":"4","key":"5_CR16","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1287\/mnsc.9.4.643","volume":"9","author":"A.A. Kuehn","year":"1963","unstructured":"Kuehn, A.A., Hamburger, M.J.: A heuristic program for locating warehouses. Management Science\u00a09(4), 643\u2013666 (1963)","journal-title":"Management Science"},{"issue":"3","key":"5_CR17","first-page":"631","volume":"45","author":"J.F. Stollsteimer","year":"1963","unstructured":"Stollsteimer, J.F.: A working model for plant numbers and locations. Management Science\u00a045(3), 631\u2013645 (1963)","journal-title":"Management Science"},{"key":"5_CR18","unstructured":"Balinski, M.L.: On finding integer solutions to linear programs. In: Proceedings of IBM Scientific Computing Symposium on Combinatorial Problems, pp. 225\u2013248 (1966)"},{"issue":"3","key":"5_CR19","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1057\/jors.1977.104","volume":"28","author":"L. Kaufman","year":"1977","unstructured":"Kaufman, L., Eede, M.V., Hansen, P.: A plant and warehouse location problem. Operational Research Quarterly\u00a028(3), 547\u2013554 (1977)","journal-title":"Operational Research Quarterly"},{"key":"5_CR20","volume-title":"Discrete Location Theory","author":"G. Cornuejols","year":"1990","unstructured":"Cornuejols, G., Nemhouser, G., Wolsey, L.: Discrete Location Theory. Wiley, Chichester (1990)"},{"issue":"1","key":"5_CR21","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"D.S. Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Heuristics for the fixed cost median problem. Mathematical Programming\u00a022(1), 148\u2013162 (1982)","journal-title":"Mathematical Programming"},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"Lin, J.H., Vitter, J.S.: e-approximations with minimum packing constraint violation (extended abstract). In: STOC 1992: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pp. 771\u2013782 (1992)","DOI":"10.1145\/129712.129787"},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, \u00c9., Aardal, K.: Approximation algorithms for facility location problems (extended abstract). In: STOC 1997: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp. 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"Moscibroda, T., Wattenhofer, R.: Facility location: distributed approximation. In: PODC 2005: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, pp. 108\u2013117 (2005)","DOI":"10.1145\/1073814.1073834"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"5_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-540-73090-3_9","volume-title":"Distributed Computing in Sensor Systems","author":"C. Frank","year":"2007","unstructured":"Frank, C., R\u00f6mer, K.: Distributed facility location algorithms for flexible configuration of wireless sensor networks. In: Aspnes, J., Scheideler, C., Arora, A., Madden, S. (eds.) DCOSS 2007. LNCS, vol.\u00a04549, pp. 124\u2013141. Springer, Heidelberg (2007)"},{"issue":"6","key":"5_CR27","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K. Jain","year":"2003","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing lp. J. ACM\u00a050(6), 795\u2013824 (2003)","journal-title":"J. ACM"},{"key":"5_CR28","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1145\/1148109.1148152","volume-title":"SPAA 2006: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures","author":"J. Gehweiler","year":"2006","unstructured":"Gehweiler, J., Lammersen, C., Sohler, C.: A distributed O(1)-approximation algorithm for the uniform facility location problem. In: SPAA 2006: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, pp. 237\u2013243. ACM, New York (2006)"},{"key":"5_CR29","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: A Log-Star Distributed Maximal Independent Set Algorithm for growth-Bounded Graphs. In: 27th ACM Symposium on Principles of Distributed Computing (PODC), Toronto, Canada (2008)","DOI":"10.1145\/1400751.1400758"},{"key":"5_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-540-75520-3_29","volume-title":"Algorithms \u2013 ESA 2007","author":"S. Pemmaraju","year":"2007","unstructured":"Pemmaraju, S., Pirwani, I.: Good quality virtual realization of unit ball graphs. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 311\u2013322. Springer, Heidelberg (2007)"},{"key":"5_CR31","unstructured":"Pandit, S., Pemmaraju, S.: Finding facilities fast. Full Paper (2009), http:\/\/cs.uiowa.edu\/~spandit\/research\/icdcn2009.pdf"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing and Networking"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92295-7_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T17:26:09Z","timestamp":1739035569000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92295-7_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540922940","9783540922957"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92295-7_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}