{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T12:49:59Z","timestamp":1725454199419},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642341052"},{"type":"electronic","value":"9783642341069"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34106-9_17","type":"book-chapter","created":{"date-parts":[[2012,10,1]],"date-time":"2012-10-01T05:56:27Z","timestamp":1349070987000},"page":"184-198","source":"Crossref","is-referenced-by-count":3,"title":["Data Stability in Clustering: A Closer Look"],"prefix":"10.1007","author":[{"given":"Lev","family":"Reyzin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_CR1","first-page":"1","volume":"5","author":"M. Ackerman","year":"2009","unstructured":"Ackerman, M., Ben-David, S.: Clusterability: A theoretical study. Journal of Machine Learning Research - Proceedings Track\u00a05, 1\u20138 (2009)","journal-title":"Journal of Machine Learning Research - Proceedings Track"},{"key":"17_CR2","unstructured":"Ailon, N., Jaiswal, R., Monteleoni, C.: Streaming k-means approximation. In: NIPS (2009)"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for euclidean-medians and related problems. In: STOC, pp. 106\u2013113 (1998)","DOI":"10.1145\/276698.276718"},{"issue":"3","key":"17_CR4","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":"17_CR5","doi-asserted-by":"crossref","unstructured":"Awasthi, P., Blum, A., Sheffet, O.: Stability yields a ptas for k-median and k-means clustering. In: FOCS, pp. 309\u2013318 (2010)","DOI":"10.1109\/FOCS.2010.36"},{"issue":"1-2","key":"17_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.ipl.2011.10.006","volume":"112","author":"P. Awasthi","year":"2012","unstructured":"Awasthi, P., Blum, A., Sheffet, O.: Center-based clustering under perturbation stability. Inf. Process. Lett.\u00a0112(1-2), 49\u201354 (2012)","journal-title":"Inf. Process. Lett."},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Balcan, M.F., Blum, A., Gupta, A.: Approximate clustering without the approximation. In: SODA (2009)","DOI":"10.1137\/1.9781611973068.116"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"Balcan, M.F., Blum, A., Vempala, S.: A discriminative framework for clustering via similarity functions. In: STOC, pp. 671\u2013680 (2008)","DOI":"10.1145\/1374376.1374474"},{"key":"17_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/978-3-642-31594-7_6","volume-title":"Automata, Languages, and Programming","author":"M.F. Balcan","year":"2012","unstructured":"Balcan, M.F., Liang, Y.: Clustering under Perturbation Resilience. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 63\u201374. Springer, Heidelberg (2012)"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Charikar, M., Raz, D.: Approximating min-sum -clustering in metric spaces. In: STOC, pp. 11\u201320 (2001)","DOI":"10.1145\/380752.380754"},{"key":"17_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/11750321_22","volume-title":"Theory and Applications of Models of Computation","author":"S. Ben-David","year":"2006","unstructured":"Ben-David, S.: Alternative Measures of Computational Complexity with Applications to Agnostic Learning. In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol.\u00a03959, pp. 231\u2013235. Springer, Heidelberg (2006)"},{"key":"17_CR12","unstructured":"Bilu, Y., Linial, N.: Are stable instances easy? In: Innovations in Computer Science, pp. 332\u2013341 (2010)"},{"issue":"1","key":"17_CR13","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, \u00c9., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem. J. Comput. Syst. Sci.\u00a065(1), 129\u2013149 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Charikar, M., O\u2019Callaghan, L., Panigrahy, R.: Better streaming algorithms for clustering problems. In: STOC, pp. 30\u201339 (2003)","DOI":"10.1145\/780547.780548"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"de la Vega, W.F., Karpinski, M., Kenyon, C., Rabani, Y.: Approximation schemes for clustering problems. In: STOC, pp. 50\u201358 (2003)","DOI":"10.1145\/780547.780550"},{"key":"17_CR16","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 & Co., New York (1979)"},{"issue":"1","key":"17_CR17","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S. Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. J. Algorithms\u00a031(1), 228\u2013248 (1999)","journal-title":"J. Algorithms"},{"issue":"3","key":"17_CR18","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1109\/TKDE.2003.1198387","volume":"15","author":"S. Guha","year":"2003","unstructured":"Guha, S., Meyerson, A., Mishra, N., Motwani, R., O\u2019Callaghan, L.: Clustering data streams: Theory and practice. IEEE Trans. Knowl. Data Eng.\u00a015(3), 515\u2013528 (2003)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: STOC, pp. 731\u2013740. ACM (2002)","DOI":"10.1145\/510008.510012"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: Linear-time approximation schemes for clustering problems in any dimensions. J. ACM\u00a057(2) (2010)","DOI":"10.1145\/1667053.1667054"},{"issue":"2","key":"17_CR21","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":"17_CR22","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. In: SODA, p. 413 (2003)"},{"key":"17_CR23","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, pp. 165\u2013176 (2006)","DOI":"10.1109\/FOCS.2006.75"},{"key":"17_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/978-3-642-14031-0_10","volume-title":"Computing and Combinatorics","author":"F. Schalekamp","year":"2010","unstructured":"Schalekamp, F., Yu, M., van Zuylen, A.: Clustering with or without the Approximation. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol.\u00a06196, pp. 70\u201379. Springer, Heidelberg (2010)"},{"key":"17_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1007\/978-3-642-18381-2_46","volume-title":"SOFSEM 2011: Theory and Practice of Computer Science","author":"J.M.M. Rooij van","year":"2011","unstructured":"van Rooij, J.M.M., van Kooten Niekerk, M.E., Bodlaender, H.L.: Partition into Triangles on Bounded Degree Graphs. In: \u010cern\u00e1, I., Gyim\u00f3thy, T., Hromkovi\u010d, J., Jefferey, K., Kr\u00e1lovi\u0107, R., Vukoli\u0107, M., Wolf, S. (eds.) SOFSEM 2011. LNCS, vol.\u00a06543, pp. 558\u2013569. Springer, Heidelberg (2011)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34106-9_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:44:55Z","timestamp":1620132295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34106-9_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642341052","9783642341069"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34106-9_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}