{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,19]],"date-time":"2026-09-19T12:13:37Z","timestamp":1789820017406,"version":"4.0.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642325113","type":"print"},{"value":"9783642325120","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_4","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T22:21:08Z","timestamp":1342822868000},"page":"37-49","source":"Crossref","is-referenced-by-count":33,"title":["Improved Spectral-Norm Bounds for Clustering"],"prefix":"10.1007","author":[{"given":"Pranjal","family":"Awasthi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Or","family":"Sheffet","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Kumar, A., Kannan, R.: Clustering with spectral norm and the k-means algorithm. In: FOCS (2010)","DOI":"10.1109\/FOCS.2010.35"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"McSherry, F.: Spectral partitioning of random graphs. In: FOCS (2001)","DOI":"10.1109\/SFCS.2001.959929"},{"key":"4_CR3","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":"4_CR4","unstructured":"Dasgupta, S.: Learning mixtures of gaussians. In: FOCS (1999)"},{"key":"4_CR5","unstructured":"Dasgupta, S., Schulman, L.: A probabilistic analysis of em for mixtures of separated, spherical gaussians. J. Mach. Learn. Res. (2007)"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Sanjeev, A., Kannan, R.: Learning mixtures of arbitrary gaussians. In: STOC (2001)","DOI":"10.1145\/380752.380808"},{"key":"4_CR7","unstructured":"Vempala, S., Wang, G.: A spectral algorithm for learning mixtures of distributions. Journal of Computer and System Sciences (2002)"},{"key":"4_CR8","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1007\/11503415_31","volume-title":"Learning Theory","author":"D. Achlioptas","year":"2005","unstructured":"Achlioptas, D., McSherry, F.: On Spectral Learning of Mixtures of Distributions. In: Auer, P., Meir, R. (eds.) COLT 2005. LNCS (LNAI), vol.\u00a03559, pp. 458\u2013469. Springer, Heidelberg (2005)"},{"key":"4_CR9","unstructured":"Chaudhuri, K., Rao, S.: Learning mixtures of product distributions using correlations and independence. In: COLT (2008)"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Kannan, R., Salmasian, H., Vempala, S.: The spectral method for general mixture models. SIAM J. Comput. (2008)","DOI":"10.1137\/S0097539704445925"},{"key":"4_CR11","unstructured":"Dasgupta, A., Hopcroft, J., Kannan, R., Mitra, P.: Spectral clustering with limited independence. In: SODA (2007)"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Brubaker, S.C., Vempala, S.: Isotropic pca and affine-invariant clustering. In: FOCS (2008)","DOI":"10.1007\/978-3-540-85221-6_8"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1017\/S0963548309990514","volume":"19","author":"A. Coja-Oghlan","year":"2010","unstructured":"Coja-Oghlan, A.: Graph partitioning via adaptive spectral techniques. Comb. Probab. Comput.\u00a019, 227\u2013284 (2010)","journal-title":"Comb. Probab. Comput."},{"key":"4_CR14","unstructured":"Awasthi, P., Sheffet, O.: Improved spectral-norm bounds for clustering, full version (2012), http:\/\/arxiv.org\/abs\/1206.3204"},{"key":"4_CR15","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: A simple linear time (1\u2009+\u2009\u03b5)-approximation algorithm for k-means clustering in any dimensions. In: FOCS (2004)"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Cohen, W.W., Richman, J.: Learning to match and cluster large high-dimensional data sets for data integration. In: KDD, pp. 475\u2013480 (2002)","DOI":"10.1145\/775107.775116"},{"issue":"4","key":"4_CR17","first-page":"536","volume":"247","author":"A.G. Murzin","year":"1995","unstructured":"Murzin, A.G., Brenner, S.E., Hubbard, T., Chothia, C.: Scop: a structural classification of proteins database for the investigation of sequences and structures. Journal of Molecular Biology\u00a0247(4), 536\u2013540 (1995)","journal-title":"Journal of Molecular Biology"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Kannan, R., Vempala, S.: Spectral algorithms. Found. Trends Theor. Comput. Sci. (March 2009)","DOI":"10.1561\/9781601982759"},{"key":"4_CR19","volume-title":"Matrix computations","author":"G.H. Golub","year":"1996","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)","edition":"3"},{"key":"4_CR20","unstructured":"Chaudhuri, K., Rao, S.: Beyond gaussians: Spectral methods for learning mixtures of heavy-tailed distributions. In: COLT (2008)"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"Kalai, A.T., Moitra, A., Valiant, G.: Efficiently learning mixtures of two gaussians. In: STOC 2010, pp. 553\u2013562 (2010)","DOI":"10.1145\/1806689.1806765"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Moitra, A., Valiant, G.: Settling the polynomial learnability of mixtures of gaussians. In: FOCS 2010 (2010)","DOI":"10.1109\/FOCS.2010.15"},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Belkin, M., Sinha, K.: Polynomial learning of distribution families. Computing Research Repository abs\/1004.4, 103\u2013112 (2010)","DOI":"10.1109\/FOCS.2010.16"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"Schulman, L.J.: Clustering for edge-cost minimization (extended abstract). In: STOC, pp. 547\u2013555 (2000)","DOI":"10.1145\/335305.335373"},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"Balcan, M.F., Blum, A., Gupta, A.: Approximate clustering without the approximation. In: SODA, pp. 1068\u20131077 (2009)","DOI":"10.1137\/1.9781611973068.116"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T03:26:19Z","timestamp":1743823579000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}