{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,6]],"date-time":"2025-04-06T11:43:53Z","timestamp":1743939833556,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540699002"},{"type":"electronic","value":"9783540699033"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-69903-3_26","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"282-293","source":"Crossref","is-referenced-by-count":6,"title":["On Metric Clustering to Minimize the Sum of Radii"],"prefix":"10.1007","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","reference":[{"key":"26_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":"26_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":"26_CR3","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":"2","key":"26_CR4","doi-asserted-by":"publisher","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.\u00a068(2), 417\u2013441 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"26_CR5","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1006\/jcss.2001.1772","volume":"63","author":"W.F. de la Vega","year":"2001","unstructured":"de la Vega, W.F., Kenyon, C.: A randomized approximation scheme for metric max-cut. J. Comput. Syst. Sci.\u00a063(4), 531\u2013541 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"26_CR6","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.\u00a07(3), 185\u2013203 (2000)","journal-title":"Nord. J. Comput."},{"key":"26_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":"26_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. W. H. Freeman, New York (1979)"},{"key":"26_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":"26_CR10","doi-asserted-by":"publisher","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 approximation algorithm for the k-center problem. Math. Oper. Res.\u00a010, 180\u2013184 (1985)","journal-title":"Math. Oper. Res."},{"key":"26_CR11","doi-asserted-by":"publisher","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.\u00a037, 539\u2013560 (1982)","journal-title":"SIAM J. Appl. Math."},{"key":"26_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: SODA, pp. 798\u2013807. SIAM, Philadelphia (2004)"},{"issue":"4","key":"26_CR13","doi-asserted-by":"publisher","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. Computer Networks\u00a047(4), 489\u2013501 (2005)","journal-title":"Computer Networks"},{"issue":"2","key":"26_CR14","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM Journal on Computing\u00a011(2), 329\u2013343 (1982)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2008"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69903-3_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T12:09:04Z","timestamp":1738325344000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-69903-3_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540699002","9783540699033"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69903-3_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}