{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T04:01:52Z","timestamp":1742529712584,"version":"3.40.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642282089"},{"type":"electronic","value":"9783642282096"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"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":[[2012]]},"DOI":"10.1007\/978-3-642-28209-6_3","type":"book-chapter","created":{"date-parts":[[2012,2,9]],"date-time":"2012-02-09T00:50:08Z","timestamp":1328748608000},"page":"13-27","source":"Crossref","is-referenced-by-count":0,"title":["Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"Abshoff","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Cord-Landwehr","sequence":"additional","affiliation":[]},{"given":"Bastian","family":"Degener","sequence":"additional","affiliation":[]},{"given":"Barbara","family":"Kempkes","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Pietrzyk","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"3_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms\u00a07(4), 567\u2013583 (1986)","journal-title":"Journal of Algorithms"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1007\/11523468_70","volume-title":"Automata, Languages and Programming","author":"M. B\u0103doiu","year":"2005","unstructured":"B\u0103doiu, M., Czumaj, A., Indyk, P., Sohler, C.: Facility Location in Sublinear Time. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 866\u2013877. Springer, Heidelberg (2005)"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Tangwongsan, K.: Parallel approximation algorithms for facility-location problems. In: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 315\u2013324 (2010)","DOI":"10.1145\/1810479.1810535"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Tangwongsan, K., Peng, R.: Linear-work greedy parallel approximation algorithms for set covering and variants. In: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA (2011)","DOI":"10.1145\/1989493.1989497"},{"key":"3_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-3-540-74208-1_3","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"J. Byrka","year":"2007","unstructured":"Byrka, J.: An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 29\u201343. Springer, Heidelberg (2007)"},{"key":"3_CR6","unstructured":"Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for a capacitated facility location problem. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 875\u2013876 (1999)"},{"issue":"3","key":"3_CR7","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1007\/s00453-008-9250-7","volume":"57","author":"B. Degener","year":"2010","unstructured":"Degener, B., Gehweiler, J., Lammersen, C.: Kinetic facility location. Algorithmica\u00a057(3), 562\u2013584 (2010)","journal-title":"Algorithmica"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Degener, B., Kempkes, B., Pietrzyk, P.: A local, distributed constant-factor approximation algorithm for the dynamic facility location problem. In: Proceedings of the 24th IEEE International Parallel & Distributed Processing Symposium (IPDPS), pp. 1\u201310. IEEE (2010)","DOI":"10.1109\/IPDPS.2010.5470349"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Gehweiler, J., Lammersen, C., Sohler, C.: A distributed $\\mathcal{O}$ (1)-approximation algorithm for the uniform facility location problem. In: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 237\u2013243 (2006)","DOI":"10.1145\/1148109.1148152"},{"issue":"1","key":"3_CR10","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S. Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. Journal of Algorithms\u00a031(1), 228\u2013248 (1999)","journal-title":"Journal of Algorithms"},{"issue":"6","key":"3_CR11","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. Journal of the ACM\u00a050(6), 795\u2013824 (2003)","journal-title":"Journal of the ACM"},{"issue":"2","key":"3_CR12","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. Journal of the ACM\u00a048(2), 274\u2013296 (2001)","journal-title":"Journal of the ACM"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 1\u201310 (1985)","DOI":"10.1145\/22145.22146"},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/3-540-45753-4_20","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M. Mahdian","year":"2002","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved Approximation Algorithms for Metric Facility Location Problems. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, pp. 229\u2013242. Springer, Heidelberg (2002)"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Mettu, R.R., Plaxton, C.G.: The online median problem. In: Proceedings of the 41st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 339\u2013348 (2000)","DOI":"10.1109\/SFCS.2000.892122"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Moscibroda, T., Wattenhofer, R.: Facility location: distributed approximation. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 108\u2013117 (2005)","DOI":"10.1145\/1073814.1073834"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Pal, M., Tardos, E.: Group strategy proof mechanisms via primal-dual algorithms. In: Proc. of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 584\u2013593 (2003)","DOI":"10.1109\/SFCS.2003.1238231"},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/978-3-540-92295-7_5","volume-title":"Distributed Computing and Networking","author":"S. Pandit","year":"2008","unstructured":"Pandit, S., Pemmaraju, S.V.: Finding Facilities Fast. In: Garg, V., Wattenhofer, R., Kothapalli, K. (eds.) ICDCN 2009. LNCS, vol.\u00a05408, pp. 11\u201324. Springer, Heidelberg (2008)"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Pandit, S., Pemmaraju, S.V.: Return of the primal-dual: distributed metric facility location. In: Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 180\u2013189 (2009)","DOI":"10.1145\/1582716.1582747"},{"key":"3_CR20","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed computing: a locality-sensitive approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)"}],"container-title":["Lecture Notes in Computer Science","Algorithms for Sensor Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28209-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,20]],"date-time":"2025-03-20T03:16:35Z","timestamp":1742440595000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28209-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642282089","9783642282096"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28209-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}