{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T22:57:56Z","timestamp":1774393076810,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540291183","type":"print"},{"value":"9783540319511","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11561071_42","type":"book-chapter","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T12:46:24Z","timestamp":1128602784000},"page":"460-471","source":"Crossref","is-referenced-by-count":45,"title":["Geometric Clustering to Minimize the Sum of Cluster Sizes"],"prefix":"10.1007","author":[{"given":"Vittorio","family":"Bil\u00f2","sequence":"first","affiliation":[]},{"given":"Ioannis","family":"Caragiannis","sequence":"additional","affiliation":[]},{"given":"Christos","family":"Kaklamanis","sequence":"additional","affiliation":[]},{"given":"Panagiotis","family":"Kanellopoulos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"42_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for the Euclidean k-medians and related problems. In: Proc. of the 30th ACM Symposium on Theory of Computing (STOC 1998), pp. 106\u2013113 (1998)","DOI":"10.1145\/276698.276718"},{"key":"42_CR2","doi-asserted-by":"crossref","unstructured":"B\u01cedoiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proc. of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002), pp. 250\u2013257 (2002)","DOI":"10.1145\/509907.509947"},{"key":"42_CR3","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Charikar, M., Raz, D.: Approximating min-sum k-clustering in metric spaces. In: Proc. of the 33rd Annual ACM Symposium on Theory of computing (STOC 2001), pp.11\u201320 (2001)","DOI":"10.1145\/380752.380754"},{"key":"42_CR4","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/978-3-642-95322-4_5","volume":"157","author":"P. Brucker","year":"1978","unstructured":"Brucker, P.: On the complexity of clustering problems. Optimization and Operations Research, Lecture Notes in Economics and Mathematical Sciences\u00a0157, 45\u201354 (1978)","journal-title":"Optimization and Operations Research, Lecture Notes in Economics and Mathematical Sciences"},{"issue":"1","key":"42_CR5","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1006\/jcss.2002.1882","volume":"65","author":"M. Charikar","year":"2002","unstructured":"Charikar, M., Guha, S., Tardos, E., Shmoys, D.S.: A constant factor approximation algorithm for the k-median problem. Journal of Computer and Systems Sciences\u00a065(1), 129\u2013149 (2002)","journal-title":"Journal of Computer and Systems Sciences"},{"issue":"2","key":"42_CR6","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. Journal of Computer and Systems Sciences\u00a068(2), 417\u2013441 (2004)","journal-title":"Journal of Computer and Systems Sciences"},{"issue":"2","key":"42_CR7","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/0196-6774(91)90007-L","volume":"12","author":"V. Capoyleas","year":"1991","unstructured":"Capoyleas, V., Rote, G., Woeginger, G.J.: Geometric Clusterings. Journal of Algorithms\u00a012(2), 341\u2013356 (1991)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"42_CR8","first-page":"185","volume":"7","author":"S.R. Doddi","year":"2000","unstructured":"Doddi, S.R., Marathe, M.V., Ravi, S.S., Taylor, D.S., Widmayer, P.: Approximation algorithms for clustering to minimize the sum of diameters. Nordic Journal of Computing\u00a07(3), 185\u2013203 (2000)","journal-title":"Nordic Journal of Computing"},{"key":"42_CR9","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric graphs. In: Proc. of the 12th Annual Symposium on Discrete Algorithms (SODA 2001), pp. 671\u2013679 (2001)"},{"key":"42_CR10","doi-asserted-by":"crossref","unstructured":"de la Vega, W.F., Karpinski, M., Kenyon, C., Rabani, Y.: Approximation schemes for clustering problems. In: Proc. of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), pp. 50\u201358 (2003)","DOI":"10.1145\/780542.780550"},{"key":"42_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/978-3-540-24592-6_11","volume-title":"Approximation and Online Algorithms","author":"A. Freund","year":"2004","unstructured":"Freund, A., Rawitz, D.: Combinatorial interpretations of dual fitting and primal fitting. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol.\u00a02909, pp. 137\u2013150. Springer, Heidelberg (2004)"},{"key":"42_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01896987","volume":"4","author":"P. Hansen","year":"1987","unstructured":"Hansen, P., Jaumard, B.: Minimum sum of diameters clustering. Journal of Classification\u00a04, 215\u2013226 (1987)","journal-title":"Journal of Classification"},{"key":"42_CR13","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 scheme and Lagrangian relaxation. Journal of the ACM\u00a048, 274\u2013296 (2001)","journal-title":"Journal of the ACM"},{"key":"42_CR14","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, 489\u2013501 (2005)","journal-title":"Computer Networks"},{"key":"42_CR15","first-page":"880","volume-title":"Graph Theory, Combinatorics and Applications","author":"C.L. Monma","year":"1991","unstructured":"Monma, C.L., Suri, S.: Partitioning points and graphs to minimize the maximum or the sum of diameters. In: Graph Theory, Combinatorics and Applications, pp. 880\u2013912. John Wiley and Sons, Chichester (1991)"},{"issue":"2","key":"42_CR16","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1145\/506147.506149","volume":"49","author":"R. Ostrovsky","year":"2002","unstructured":"Ostrovsky, R., Rabani, Y.: Polynomial-time approximation schemes for geometric clustering problems. Journal of the ACM\u00a049(2), 139\u2013156 (2002)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11561071_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:13:32Z","timestamp":1619507612000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11561071_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540291183","9783540319511"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11561071_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}