{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:44:20Z","timestamp":1792111460074,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":15,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_767","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T15:32:23Z","timestamp":1553095943000},"page":"331-335","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Clustering Under Stability Assumptions"],"prefix":"10.1007","author":[{"given":"Pranjal","family":"Awasthi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"issue":"3","key":"767_CR3240","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 (2004) Local search heuristics for k-median and facility location problems. SIAM J Comput 33(3):544\u2013562","journal-title":"SIAM J Comput"},{"key":"767_CR3241","doi-asserted-by":"crossref","unstructured":"Awasthi P, Blum A, Sheffet O (2010) Stability yields a PTAS for k-median and k-means clustering. In: Proceedings of the 2010 IEEE 51st annual symposium on foundations of computer science, Las Vegas","DOI":"10.1109\/FOCS.2010.36"},{"issue":"1\u20132","key":"767_CR3242","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 (2012) Center-based clustering under perturbation stability. Inf Process Lett 112(1\u20132):49\u201354","journal-title":"Inf Process Lett"},{"key":"767_CR3243","doi-asserted-by":"crossref","unstructured":"Balcan M-F, Liang Y (2012) Clustering under perturbation resilience. In: Proceedings of the 39th international colloquium on automata, languages and programming, Warwick","DOI":"10.1007\/978-3-642-31594-7_6"},{"key":"767_CR3244","volume-title":"Proceedings of the ACM-SIAM symposium on discrete algorithms, New York","author":"M-F Balcan","year":"2009","unstructured":"Balcan M-F, Blum A, Gupta A (2009) Approximate clustering without the approximation. In: Proceedings of the ACM-SIAM symposium on discrete algorithms, New York"},{"key":"767_CR3245","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2450142.2450144","volume":"60","author":"M-F Balcan","year":"2013","unstructured":"Balcan M-F, Blum A, Gupta A (2013) Clustering under approximation stability. J ACM 60:1\u201334","journal-title":"J ACM"},{"key":"767_CR3246","volume-title":"Proceedings of the first symposium on innovations in computer science, Beijing","author":"Y Bilu","year":"2010","unstructured":"Bilu Y, Linial N (2010) Are stable instances easy? In: Proceedings of the first symposium on innovations in computer science, Beijing"},{"key":"767_CR3247","volume-title":"Proceedings of the thirty-first annual ACM symposium on theory of computing, Atlanta","author":"M Charikar","year":"1999","unstructured":"Charikar M, Guha S, Tardos E, Shmoy DB (1999) A constant-factor approximation algorithm for the k-median problem. In: Proceedings of the thirty-first annual ACM symposium on theory of computing, Atlanta"},{"key":"767_CR3248","doi-asserted-by":"crossref","unstructured":"Jain K, Mahdian M, Saberi A (2002) A new greedy approach for facility location problems. In: Proceedings of the 34th annual ACM symposium on theory of computing, Montreal","DOI":"10.1145\/509907.510012"},{"key":"767_CR3249","volume-title":"Proceedings of the eighteenth annual symposium on computational geometry","author":"T Kanungo","year":"2002","unstructured":"Kanungo T, Mount DM, Netanyahu NS, Piatko CD, Silverman R, Wu AY (2002) A local search approximation algorithm for k-means clustering. In: Proceedings of the eighteenth annual symposium on computational geometry. ACM, New York"},{"key":"767_CR3250","doi-asserted-by":"crossref","unstructured":"Kumar A, Kannan R (2010) Clustering with spectral norm and the k-means algorithm. In: Proceedings of the 51st annual IEEE symposium on foundations of computer science, Las Vegas","DOI":"10.1109\/FOCS.2010.35"},{"key":"767_CR3251","unstructured":"Kumar A, Sabharwal Y, Sen S (2004) A simple linear time (1 +\u03b5)-approximation algorithm for k-means clustering in any dimensions. In: Proceedings of the 45th annual IEEE symposium on foundations of computer science, Washington, DC"},{"issue":"2","key":"767_CR3252","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"SP Lloyd","year":"1982","unstructured":"Lloyd SP (1982) Least squares quantization in PCM. IEEE Trans Inf Theory 28(2):129\u2013137","journal-title":"IEEE Trans Inf Theory"},{"key":"767_CR3253","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.67","volume-title":"Bilu-linial stable instances of max cut and minimum multiway cut","author":"K Makarychev","year":"2014","unstructured":"Makarychev K, Makarychev Y, Vijayaraghavan A (2014) Bilu-linial stable instances of max cut and minimum multiway cut. In: SODA, Portland"},{"key":"767_CR3254","doi-asserted-by":"crossref","unstructured":"Ostrovsky R, Rabani Y, Schulman L, Swamy C (2006) The effectiveness of lloyd-type methods for the k-means problem. In: Proceedings of the 47th annual IEEE symposium on foundations of computer science, Berkeley","DOI":"10.1109\/FOCS.2006.75"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_767","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:48:28Z","timestamp":1792108108000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_767"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_767","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}