{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:53:26Z","timestamp":1725558806121},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642140303"},{"type":"electronic","value":"9783642140310"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14031-0_10","type":"book-chapter","created":{"date-parts":[[2010,6,28]],"date-time":"2010-06-28T09:50:06Z","timestamp":1277718606000},"page":"70-79","source":"Crossref","is-referenced-by-count":2,"title":["Clustering with or without the Approximation"],"prefix":"10.1007","author":[{"given":"Frans","family":"Schalekamp","sequence":"first","affiliation":[]},{"given":"Michael","family":"Yu","sequence":"additional","affiliation":[]},{"given":"Anke","family":"van Zuylen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","unstructured":"Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: SODA \u201907: 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1027\u20131035 (2007)"},{"issue":"3","key":"10_CR2","doi-asserted-by":"publisher","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.\u00a033(3), 544\u2013562 (2004)","journal-title":"SIAM J. Comput."},{"key":"10_CR3","unstructured":"Asuncion, A., Newman, D.: UCI machine learning repository (2007), \n                    \n                      http:\/\/www.ics.uci.edu\/~mlearn\/MLRepository.html"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Balcan, M.-F., Blum, A., Gupta, A.: Approximate clustering without the approximation. In: SODA \u201909: 19th Annual ACM -SIAM Symposium on Discrete Algorithms, pp. 1068\u20131077 (2009)","DOI":"10.1137\/1.9781611973068.116"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Balcan, M.-F., Blum, A., Vempala, S.: A discriminative framework for clustering via similarity functions. In: STOC 2008: 40th Annual ACM Symposium on Theory of Computing, pp. 671\u2013680 (2008)","DOI":"10.1145\/1374376.1374474"},{"key":"10_CR6","unstructured":"Balcan, M.-F., Braverman, M.: Finding low error clusterings. In: COLT 2009: 22nd Annual Conference on Learning Theory (2009)"},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/978-3-642-04414-4_31","volume-title":"Algorithmic Learning Theory","author":"M.-F. Balcan","year":"2009","unstructured":"Balcan, M.-F., R\u00f6glin, H., Teng, S.-H.: Agnostic clustering. In: Gavald\u00e0, R., Lugosi, G., Zeugmann, T., Zilles, S. (eds.) ALT 2009. LNCS, vol.\u00a05809, pp. 384\u2013398. Springer, Heidelberg (2009)"},{"issue":"2","key":"10_CR8","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0377-2217(85)90040-2","volume":"21","author":"J.E. Beasley","year":"1985","unstructured":"Beasley, J.E.: A note on solving large p-median problems. European Journal of Operational Research\u00a021(2), 270\u2013273 (1985)","journal-title":"European Journal of Operational Research"},{"key":"10_CR9","unstructured":"Beasley, J.E.: OR-Library p-median - uncapacitated (1985), \n                    \n                      http:\/\/people.brunel.ac.uk\/~mastjjb\/jeb\/orlib\/pmedinfo.html"},{"key":"10_CR10","unstructured":"Bilu, Y., Linial, N.: Are stable instances easy. In: ICS 2010: The First Symposium on Innovations in Computer Science, pp. 332\u2013341 (2010)"},{"key":"10_CR11","unstructured":"Gupta, A.: Personal Communication (2009)"},{"issue":"6","key":"10_CR12","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. J. ACM\u00a050(6), 795\u2013824 (2003)","journal-title":"J. ACM"},{"issue":"2","key":"10_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 schema and Lagrangian relaxation. J. ACM\u00a048(2), 274\u2013296 (2001)","journal-title":"J. ACM"},{"issue":"2","key":"10_CR14","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S. Lloyd","year":"1982","unstructured":"Lloyd, S.: Least squares quantization in PCM. IEEE Transactions on Information Theory\u00a028(2), 129\u2013137 (1982)","journal-title":"IEEE Transactions on Information Theory"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rabani, Y., Schulman, L.J., Swamy, C.: The effectiveness of Lloyd-type methods for the k-means problem. In: FOCS \u201906:47th Annual IEEE Symposium on Foundations of Computer Science, pp. 165\u2013176 (2006)","DOI":"10.1109\/FOCS.2006.75"},{"key":"10_CR16","unstructured":"Schalekamp, F., Yu, M., van Zuylen, A.: Clustering with or without the approximation, \n                    \n                      http:\/\/www.itcs.tsinghua.edu.cn\/~frans\/pub\/ClustCOCOON.pdf"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14031-0_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T03:44:44Z","timestamp":1552621484000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14031-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642140303","9783642140310"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14031-0_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}