{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,19]],"date-time":"2026-04-19T05:56:41Z","timestamp":1776578201318,"version":"3.51.2"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,2,12]],"date-time":"2009-02-12T00:00:00Z","timestamp":1234396800000},"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":[[2010,7]]},"DOI":"10.1007\/s00453-009-9282-7","type":"journal-article","created":{"date-parts":[[2009,2,11]],"date-time":"2009-02-11T18:29:16Z","timestamp":1234376956000},"page":"484-498","source":"Crossref","is-referenced-by-count":23,"title":["On Metric Clustering to Minimize the Sum of Radii"],"prefix":"10.1007","volume":"57","author":[{"given":"Matt","family":"Gibson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gaurav","family":"Kanade","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik","family":"Krohn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Imran A.","family":"Pirwani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kasturi","family":"Varadarajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,2,12]]},"reference":[{"key":"9282_CR1","first-page":"449","volume-title":"Symposium on Computational Geometry","author":"H. Alt","year":"2006","unstructured":"Alt, H., Arkin, E.M., Br\u00f6nnimann, H., Erickson, J., Fekete, S.P., Knauer, C., Lenchner, J., Mitchell, J.S.B., Whittlesey, K.: Minimum-cost coverage of point sets by disks. In: Amenta, N., Cheong, O. (eds.) Symposium on Computational Geometry, pp. 449\u2013458. ACM, New York (2006)"},{"key":"9282_CR2","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: FOCS, pp. 184\u2013193 (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"key":"9282_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1007\/11561071_42","volume-title":"ESA","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: St\u00f8lting Brodal, G., Leonardi, S. (eds.) ESA. Lecture Notes in Computer Science, vol. 3669, pp. 460\u2013471. Springer, Berlin (2005)"},{"issue":"2","key":"9282_CR4","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/j.jcss.2003.07.014","volume":"68","author":"M. Charikar","year":"2004","unstructured":"Charikar, M., Panigrahy, R.: Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci. 68(2), 417\u2013441 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9282_CR5","first-page":"185","volume":"7","author":"S. Doddi","year":"2000","unstructured":"Doddi, S., Marathe, M.V., Ravi, S.S., Taylor, D.S., Widmayer, P.: Approximation algorithms for clustering to minimize the sum of diameters. Nord. J. Comput. 7(3), 185\u2013203 (2000)","journal-title":"Nord. J. Comput."},{"issue":"4","key":"9282_CR6","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1006\/jcss.2001.1772","volume":"63","author":"W. Fernandez de la Vega","year":"2001","unstructured":"Fernandez de la Vega, W., Kenyon, C.: A randomized approximation scheme for metric max-cut. J.\u00a0Comput. Syst. Sci. 63(4), 531\u2013541 (2001)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9282_CR7","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1145\/780542.780608","volume-title":"STOC","author":"J. Fakcharoenphol","year":"2003","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: STOC, pp. 448\u2013455. ACM, New York (2003)"},{"key":"9282_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9282_CR9","first-page":"819","volume-title":"SODA","author":"M. Gibson","year":"2008","unstructured":"Gibson, M., Kanade, G., Krohn, E., Pirwani, I.A., Varadarajan, K.: On clustering to minimize the sum of radii. In: SODA, pp. 819\u2013825. SIAM, Philadelphia (2008)"},{"key":"9282_CR10","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"D.S. Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the k-center problem. Math. Oper. Res. 10, 180\u2013184 (1985)","journal-title":"Math. Oper. Res."},{"key":"9282_CR11","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1137\/0137041","volume":"37","author":"O. Kariv","year":"1982","unstructured":"Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems. Part II: The p-medians. SIAM J. Appl. Math. 37, 539\u2013560 (1982)","journal-title":"SIAM J. Appl. Math."},{"key":"9282_CR12","first-page":"798","volume-title":"SODA","author":"R. Krauthgamer","year":"2004","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: Munro, J.I. (ed.) SODA, pp. 798\u2013807. SIAM, Philadelphia (2004)"},{"issue":"4","key":"9282_CR13","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1016\/j.comnet.2004.08.012","volume":"47","author":"N. Lev-Tov","year":"2005","unstructured":"Lev-Tov, N., Peleg, D.: Polynomial time approximation schemes for base station coverage with minimum total radii. Comput. Netw. 47(4), 489\u2013501 (2005)","journal-title":"Comput. Netw."},{"issue":"2","key":"9282_CR14","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9282_CR15","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"M.S. Manasse","year":"1990","unstructured":"Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. J. Algorithms 11(2), 208\u2013230 (1990)","journal-title":"J. Algorithms"},{"issue":"1","key":"9282_CR16","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","volume":"1","author":"S.E. Schaeffer","year":"2007","unstructured":"Schaeffer, S.E.: Graph clustering. Comput. Sci. Rev. 1(1), 27\u201364 (2007)","journal-title":"Comput. Sci. Rev."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9282-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9282-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9282-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,23]],"date-time":"2023-05-23T23:52:32Z","timestamp":1684885952000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9282-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,12]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["9282"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9282-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2,12]]}}}