{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T09:30:51Z","timestamp":1649064651084},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,2,4]],"date-time":"2011-02-04T00:00:00Z","timestamp":1296777600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2013,4]]},"DOI":"10.1007\/s10878-011-9382-6","type":"journal-article","created":{"date-parts":[[2011,2,3]],"date-time":"2011-02-03T16:35:26Z","timestamp":1296750926000},"page":"393-429","source":"Crossref","is-referenced-by-count":0,"title":["Clustering with or without the approximation"],"prefix":"10.1007","volume":"25","author":[{"given":"Frans","family":"Schalekamp","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anke","family":"van Zuylen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,2,4]]},"reference":[{"key":"9382_CR1","first-page":"106","volume-title":"STOC \u201998: proceedings of the 30th annual ACM symposium on theory of computing","author":"S Arora","year":"1999","unstructured":"Arora S, Raghavan P, Rao S (1999) Approximation schemes for Euclidean k-medians and related problems. In: STOC \u201998: proceedings of the 30th annual ACM symposium on theory of computing, pp\u00a0106\u2013113"},{"key":"9382_CR2","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/1137856.1137880","volume-title":"SCG \u201906: 22d annual symposium on computational geometry","author":"D Arthur","year":"2006","unstructured":"Arthur D, Vassilvitskii S (2006) How slow is the k-means method? In: SCG \u201906: 22d annual symposium on computational geometry, pp\u00a0144\u2013153"},{"key":"9382_CR3","first-page":"1027","volume-title":"SODA \u201907: 18th annual ACM-SIAM symposium on discrete algorithms","author":"D Arthur","year":"2007","unstructured":"Arthur D, Vassilvitskii S (2007) k-means++: the advantages of careful seeding. In: SODA \u201907: 18th annual ACM-SIAM symposium on discrete algorithms, pp\u00a01027\u20131035"},{"issue":"3","key":"9382_CR4","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 (2004) Local search heuristics for k-median and facility location problems. SIAM J Comput 33(3):544\u2013562","journal-title":"SIAM J Comput"},{"key":"9382_CR5","unstructured":"Asuncion A, Newman D (2007) UCI machine learning repository. http:\/\/www.ics.uci.edu\/mlearn\/MLRepository.html"},{"key":"9382_CR6","unstructured":"Awasthi P, Blum A, Sheffet O (2010) Clustering under natural stability assumptions. http:\/\/repository.cmu.edu\/compsci\/123\/ , retrieved on June 9th, 2010"},{"key":"9382_CR7","volume-title":"COLT 2009: 22nd annual conference on learning theory","author":"MF Balcan","year":"2009","unstructured":"Balcan MF, Braverman M (2009) Finding low error clusterings. In: COLT 2009: 22nd annual conference on learning theory"},{"key":"9382_CR8","first-page":"671","volume-title":"STOC 2008: 40th annual ACM symposium on theory of computing","author":"MF Balcan","year":"2008","unstructured":"Balcan MF, Blum A, Vempala S (2008) A discriminative framework for clustering via similarity functions. In: STOC 2008: 40th annual ACM symposium on theory of computing, pp\u00a0671\u2013680"},{"key":"9382_CR9","doi-asserted-by":"crossref","first-page":"1068","DOI":"10.1137\/1.9781611973068.116","volume-title":"SODA \u201909: 19th annual ACM-SIAM symposium on discrete algorithms","author":"MF Balcan","year":"2009","unstructured":"Balcan MF, Blum A, Gupta A (2009a) Approximate clustering without the approximation. In: SODA \u201909: 19th annual ACM-SIAM symposium on discrete algorithms, pp\u00a01068\u20131077"},{"key":"9382_CR10","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1007\/978-3-642-04414-4_31","volume-title":"ALT 2009: 20th international conference on algorithmic learning theory","author":"MF Balcan","year":"2009","unstructured":"Balcan MF, R\u00f6glin H, Teng SH (2009b) Agnostic clustering. In: ALT 2009: 20th international conference on algorithmic learning theory. Lecture notes in computer science, vol 5809. Springer, Berlin, pp 384\u2013398"},{"key":"9382_CR11","volume-title":"UAI 2010: the 26th conference on uncertainty in artificial intelligence","author":"MF Balcan","year":"2010","unstructured":"Balcan MF, R\u00f6glin H, Teng S, Voevodski K, Xia Y (2010) Efficient clustering with limited distance information. In: UAI 2010: the 26th conference on uncertainty in artificial intelligence"},{"issue":"2","key":"9382_CR12","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0377-2217(85)90040-2","volume":"21","author":"JE Beasley","year":"1985","unstructured":"Beasley JE (1985a) A note on solving large p-median problems. Eur J Oper Res 21(2):270\u2013273","journal-title":"Eur J Oper Res"},{"key":"9382_CR13","unstructured":"Beasley JE (1985b) OR-Library p-median\u2014uncapacitated. http:\/\/people.brunel.ac.uk\/mastjjb\/jeb\/orlib\/pmedinfo.html"},{"key":"9382_CR14","first-page":"332","volume-title":"ICS 2010: the first symposium on innovations in computer science","author":"Y Bilu","year":"2010","unstructured":"Bilu Y, Linial N (2010) Are stable instances easy? In: ICS 2010: the first symposium on innovations in computer science, pp 332\u2013341"},{"issue":"4","key":"9382_CR15","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1137\/S0097539701398594","volume":"34","author":"M Charikar","year":"2005","unstructured":"Charikar M, Guha S (2005) Improved combinatorial algorithms for facility location problems. SIAM J Comput 34(4):803\u2013824 (electronic)","journal-title":"SIAM J Comput"},{"issue":"1","key":"9382_CR16","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1006\/jcss.2002.1882","volume":"65","author":"M Charikar","year":"2002","unstructured":"Charikar M, Guha S, Tardos \u00c9, Shmoys DB (2002) A constant-factor approximation algorithm for the k-median problem. J Comput Syst Sci 65(1):129\u2013149","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"9382_CR17","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U (1998) A threshold of ln\u2009n for approximating set cover. J ACM 45(4):634\u2013652","journal-title":"J ACM"},{"key":"9382_CR18","unstructured":"Gupta A (2009) personal communication"},{"issue":"2","key":"9382_CR19","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain K, Vazirani VV (2001) Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J ACM 48(2):274\u2013296","journal-title":"J ACM"},{"issue":"6","key":"9382_CR20","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 VV (2003) Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J ACM 50(6):795\u2013824","journal-title":"J ACM"},{"issue":"2","key":"9382_CR21","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S Lloyd","year":"1982","unstructured":"Lloyd S (1982) Least squares quantization in PCM. IEEE Trans Inf Theory 28(2):129\u2013137","journal-title":"IEEE Trans Inf Theory"},{"key":"9382_CR22","first-page":"165","volume-title":"FOCS \u201906: 47th annual IEEE symposium on foundations of computer science","author":"R Ostrovsky","year":"2006","unstructured":"Ostrovsky R, Rabani Y, Schulman LJ, Swamy C (2006) 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"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-011-9382-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-011-9382-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-011-9382-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,8]],"date-time":"2019-06-08T09:35:26Z","timestamp":1559986526000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-011-9382-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2,4]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["9382"],"URL":"https:\/\/doi.org\/10.1007\/s10878-011-9382-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2,4]]}}}