{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,13]],"date-time":"2024-08-13T06:34:45Z","timestamp":1723530885260},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,9,20]],"date-time":"2012-09-20T00:00:00Z","timestamp":1348099200000},"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":[[2014,3]]},"DOI":"10.1007\/s00453-012-9690-y","type":"journal-article","created":{"date-parts":[[2012,9,19]],"date-time":"2012-09-19T17:01:24Z","timestamp":1348074084000},"page":"643-670","source":"Crossref","is-referenced-by-count":6,"title":["A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem"],"prefix":"10.1007","volume":"68","author":[{"given":"Joachim","family":"Gehweiler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christiane","family":"Lammersen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,9,20]]},"reference":[{"issue":"3","key":"9690_CR1","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V. Arya","year":"2004","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544\u2013562 (2004)","journal-title":"SIAM J. Comput."},{"key":"9690_CR2","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1007\/11523468_70","volume-title":"Proceedings of the 32nd Annual International Colloquium on Automata, Languages and Programming (ICALP\u201905)","author":"M. B\u0103doiu","year":"2005","unstructured":"B\u0103doiu, M., Czumaj, A., Indyk, P., Sohler, C.: Facility location in sublinear time. In: Proceedings of the 32nd Annual International Colloquium on Automata, Languages and Programming (ICALP\u201905), vol. 3580, pp. 866\u2013877. Springer, Berlin (2005)"},{"issue":"6","key":"9690_CR3","doi-asserted-by":"crossref","first-page":"2212","DOI":"10.1137\/070708901","volume":"39","author":"J. Byrka","year":"2010","unstructured":"Byrka, J., Aardal, K.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J. Comput. 39(6), 2212\u20132231 (2010)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9690_CR4","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1137\/S0097539701398594","volume":"34","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34(4), 803\u2013824 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9690_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539703405754","volume":"33","author":"F.A. Chudak","year":"2003","unstructured":"Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33(1), 1\u201325 (2003)","journal-title":"SIAM J. Comput."},{"key":"9690_CR6","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1145\/1281100.1281111","volume-title":"Proceedings of the 26th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC\u201907)","author":"B. Gfeller","year":"2007","unstructured":"Gfeller, B., Vicari, E.: A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. In: Proceedings of the 26th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC\u201907), pp. 53\u201360. Association for Computing Machinery, New York (2007)"},{"issue":"1","key":"9690_CR7","doi-asserted-by":"crossref","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. J. Algorithms 31(1), 228\u2013248 (1999)","journal-title":"J. Algorithms"},{"issue":"6","key":"9690_CR8","doi-asserted-by":"crossref","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 (JACM) 50(6), 795\u2013824 (2003)","journal-title":"J. ACM (JACM)"},{"key":"9690_CR9","first-page":"731","volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC\u201902)","author":"K. Jain","year":"2002","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC\u201902), pp. 731\u2013740. Association for Computing Machinery, New York (2002)"},{"issue":"2","key":"9690_CR10","doi-asserted-by":"crossref","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 (JACM) 48(2), 274\u2013296 (2001)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"9690_CR11","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"M.R. Korupolu","year":"2000","unstructured":"Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. J. Algorithms 37(1), 146\u2013188 (2000)","journal-title":"J. Algorithms"},{"key":"9690_CR12","volume-title":"Distributed Algorithms","author":"N.A. Lynch","year":"1996","unstructured":"Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, San Mateo (1996)"},{"issue":"2","key":"9690_CR13","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/S0097539703435716","volume":"36","author":"M. Mahdian","year":"2006","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility location problems. SIAM J. Comput. 36(2), 411\u2013432 (2006)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9690_CR14","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1137\/S0097539701383443","volume":"32","author":"R.R. Mettu","year":"2003","unstructured":"Mettu, R.R., Plaxton, C.G.: The online median problem. SIAM J. Comput. 32(3), 816\u2013832 (2003)","journal-title":"SIAM J. Comput."},{"key":"9690_CR15","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1145\/1073814.1073834","volume-title":"Proceedings of the 24th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC\u201905)","author":"T. Moscibroda","year":"2005","unstructured":"Moscibroda, T., Wattenhofer, R.: Facility location: Distributed approximation. In: Proceedings of the 24th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC\u201905), pp. 108\u2013117. Association for Computing Machinery, New York (2005)"},{"key":"9690_CR16","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1145\/1582716.1582747","volume-title":"Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing (PODC\u201909)","author":"S. Pandit","year":"2009","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\u201909), pp. 180\u2013189. Association for Computing Machinery, New York (2009)"},{"key":"9690_CR17","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"9690_CR18","first-page":"265","volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC\u201997)","author":"D.B. Shmoys","year":"1997","unstructured":"Shmoys, D.B., Tardos, \u00c9., Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC\u201997), pp. 265\u2013274. Association for Computing Machinery, New York (1997)"},{"key":"9690_CR19","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/3-540-47867-1_18","volume-title":"Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201902)","author":"M. Sviridenko","year":"2002","unstructured":"Sviridenko, M.: An improved approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201902), pp. 240\u2013257. Springer, Berlin (2002)"},{"issue":"2","key":"9690_CR20","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1137\/S0097539701388884","volume":"34","author":"M. Thorup","year":"2004","unstructured":"Thorup, M.: Quick k-median, k-center, and facility location for sparse graphs. SIAM J. Comput. 34(2), 405\u2013432 (2004)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9690-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9690-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9690-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,29]],"date-time":"2022-01-29T11:11:28Z","timestamp":1643454688000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9690-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,20]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["9690"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9690-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,20]]}}}