{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:51Z","timestamp":1740109311487,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T00:00:00Z","timestamp":1665014400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T00:00:00Z","timestamp":1665014400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-19-1-2322"],"award-info":[{"award-number":["N00014-19-1-2322"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s10107-022-01886-5","type":"journal-article","created":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T14:02:54Z","timestamp":1665064974000},"page":"357-423","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["k-median: exact recovery in the extended stochastic ball model"],"prefix":"10.1007","volume":"200","author":[{"given":"Alberto","family":"Del Pia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4068-5537","authenticated-orcid":false,"given":"Mingchen","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,6]]},"reference":[{"issue":"177","key":"1886_CR1","first-page":"1","volume":"18","author":"E Abbe","year":"2018","unstructured":"Abbe, E.: Community detection and stochastic block models: recent developments. J. Mach. Learn. Res. 18(177), 1\u201386 (2018)","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"1886_CR2","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1109\/TIT.2015.2490670","volume":"62","author":"E Abbe","year":"2016","unstructured":"Abbe, E., Bandeira, A., Hall, G.: Exact recovery in the stochastic block model. IEEE Trans. Inf. Theory 62(1), 471\u2013487 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1886_CR3","first-page":"125","volume-title":"Multisection in the Stochastic Block Model Using Semidefinite Programming","author":"N Agarwal","year":"2017","unstructured":"Agarwal, N., Bandeira, A., Koiliaris, K., Kolla, A.: Multisection in the Stochastic Block Model Using Semidefinite Programming, pp. 125\u2013162. Springer, Cham (2017)"},{"issue":"1","key":"1886_CR4","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s10107-013-0729-x","volume":"147","author":"B Ames","year":"2014","unstructured":"Ames, B.: Guaranteed clustering and biclustering via semidefinite programming. Math. Program. 147(1), 429\u2013465 (2014)","journal-title":"Math. Program."},{"issue":"1","key":"1886_CR5","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s10107-013-0733-1","volume":"143","author":"B Ames","year":"2014","unstructured":"Ames, B., Vavasis, S.: Convex optimization for the planted $$k$$-disjoint-clique problem. Math. Program. 143(1), 299\u2013337 (2014)","journal-title":"Math. Program."},{"issue":"1","key":"1886_CR6","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1214\/17-AOS1545","volume":"46","author":"A Amini","year":"2018","unstructured":"Amini, A., Levina, E.: On semidefinite relaxations for the block model. Ann. Stat. 46(1), 149\u2013179 (2018)","journal-title":"Ann. Stat."},{"doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Polynomial time approximation schemes for Euclidean k-medians and related problems. In: ACM STOC, vol. 98 (1998)","key":"1886_CR7","DOI":"10.1145\/276698.276718"},{"issue":"3","key":"1886_CR8","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. 33(3), 544\u2013562 (2004)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Awasthi, P., Bandeira, A., Charikar, M., Krishnaswamy, R., Villar, S., Ward, R.: Relax, no need to round: integrality of clustering formulations. Preprint arXiv:1408.4045 (2015)","key":"1886_CR9","DOI":"10.1145\/2688073.2688116"},{"doi-asserted-by":"crossref","unstructured":"Awasthi, P., Bandeira, A., Charikar, M., Krishnaswamy, R., Villar, S., Ward, R.: Relax, no need to round: integrality of clustering formulations. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pp. 191\u2013200 (2015)","key":"1886_CR10","DOI":"10.1145\/2688073.2688116"},{"key":"1886_CR11","volume-title":"Introduction to Linear Optimization","author":"D Bertsimas","year":"1997","unstructured":"Bertsimas, D., Tsitsiklis, J.: Introduction to Linear Optimization. Athena Scientific, Belmont (1997)"},{"doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and $$k$$-median problems. In: 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pp. 378\u2013388. IEEE (1999)","key":"1886_CR12","DOI":"10.1109\/SFFCS.1999.814609"},{"issue":"1","key":"1886_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.: A constant-factor approximation algorithm for the $$k$$-median problem. J. Comput. Syst. Sci. 65(1), 129\u2013149 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1886_CR14","first-page":"2213","volume":"15","author":"Y Chen","year":"2014","unstructured":"Chen, Y., Jalali, A., Sanghavi, S., Xu, H.: Clustering partially observed graphs via convex optimization. J. Mach. Learn. Res. 15(1), 2213\u20132238 (2014)","journal-title":"J. Mach. Learn. Res."},{"issue":"10","key":"1886_CR15","doi-asserted-by":"publisher","first-page":"6440","DOI":"10.1109\/TIT.2014.2346205","volume":"60","author":"Y Chen","year":"2014","unstructured":"Chen, Y., Sanghavi, S., Xu, H.: Improved graph clustering. IEEE Trans. Inf. Theory 60(10), 6440\u20136455 (2014)","journal-title":"IEEE Trans. Inf. Theory"},{"unstructured":"De\u00a0Rosa, A., Khajavirad, A.: The ratio-cut polytope and $$k$$-means clustering. Preprint arXiv:2006.15225 (2020)","key":"1886_CR16"},{"unstructured":"Del\u00a0Pia, A., Khajavirad, A., Kunisky, D.: Linear programming and community detection. Preprint arXiv:2006.03213 (2020)","key":"1886_CR17"},{"key":"1886_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511779398","volume-title":"Probability: Theory and Examples. Cambridge Series in Statistical and Probabilistic Mathematics","author":"R Durrett","year":"2010","unstructured":"Durrett, R.: Probability: Theory and Examples. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (2010)"},{"unstructured":"Fei, Y., Chen, Y.: Hidden integrality of SDP relaxations for sub-gaussian mixture models. In: Conference On Learning Theory, COLT 2018, Proceedings of Machine Learning Research, vol.\u00a075, pp. 1931\u20131965 (2018)","key":"1886_CR19"},{"issue":"5","key":"1886_CR20","doi-asserted-by":"publisher","first-page":"2788","DOI":"10.1109\/TIT.2016.2546280","volume":"62","author":"B Hajek","year":"2016","unstructured":"Hajek, B., Wu, Y., Xu, J.: Achieving exact cluster recovery threshold via semidefinite programming. IEEE Trans. Inf. Theory 62(5), 2788\u20132797 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1886_CR21","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/s10107-016-1097-0","volume":"165","author":"T Iguchi","year":"2017","unstructured":"Iguchi, T., Mixon, D., Peterson, J., Villar, S.: Probably certifiably correct $$k$$-means clustering. Math. Program. Ser. A 165, 605\u2013642 (2017)","journal-title":"Math. Program. Ser. A"},{"issue":"3","key":"1886_CR22","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0137041","volume":"37","author":"O Kariv","year":"1979","unstructured":"Kariv, O., Hakimi, S.: An algorithmic approach to network location problems, part II: $$p$$-medians. SIAM J. Appl. Math. 37(3), 539\u2013560 (1979)","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"1886_CR23","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1137\/S0097539702404055","volume":"37","author":"S Kolliopoulos","year":"2007","unstructured":"Kolliopoulos, S., Rao, S.: A nearly linear-time approximation scheme for the Euclidean $$k$$-median problem. SIAM J. Comput. 37(3), 757\u2013782 (2007)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1886_CR24","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1214\/19-STS715","volume":"36","author":"X Li","year":"2021","unstructured":"Li, X., Chen, Y., Xu, J.: Convex relaxation methods for community detection. Stat. Sci. 36(1), 2\u201315 (2021)","journal-title":"Stat. Sci."},{"issue":"1","key":"1886_CR25","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s10107-018-1333-x","volume":"179","author":"X Li","year":"2020","unstructured":"Li, X., Li, Y., Ling, S., Strohmer, T., Wei, K.: When do birds of a feather flock together? $$k$$-means, proximity, and conic programming. Math. Program. 179(1), 295\u2013341 (2020)","journal-title":"Math. Program."},{"issue":"5","key":"1886_CR26","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0020-0190(92)90208-D","volume":"44","author":"J Lin","year":"1992","unstructured":"Lin, J., Vitter, J.: Approximation algorithms for geometric median problems. Inf. Process. Lett. 44(5), 245\u2013249 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"1886_CR27","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s10208-019-09421-3","volume":"20","author":"S Ling","year":"2020","unstructured":"Ling, S., Strohmer, T.: Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering. Found. Comput. Math. 20(3), 367\u2013421 (2020)","journal-title":"Found. Comput. Math."},{"issue":"1","key":"1886_CR28","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N., Supowit, K.: On the complexity of some common geometric location problems. SIAM J. Comput. 13(1), 182\u2013196 (1984)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1886_CR29","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1134\/S0001434620030189","volume":"107","author":"B Mityagin","year":"2020","unstructured":"Mityagin, B.: The zero set of a real analytic function. Math. Notes 107(3), 529\u2013530 (2020)","journal-title":"Math. Notes"},{"issue":"4","key":"1886_CR30","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1093\/imaiai\/iax001","volume":"6","author":"D Mixon","year":"2017","unstructured":"Mixon, D., Villar, S., Ward, R.: Clustering subgaussian mixtures by semidefinite programming. Inf. Inference A J. IMA 6(4), 389\u2013415 (2017)","journal-title":"Inf. Inference A J. IMA"},{"key":"1886_CR31","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.ic.2015.09.002","volume":"245","author":"A Nellore","year":"2015","unstructured":"Nellore, A., Ward, R.: Recovery guarantees for exemplar-based clustering. Inf. Comput. 245, 165\u2013180 (2015)","journal-title":"Inf. Comput."},{"issue":"1","key":"1886_CR32","first-page":"1007","volume":"20","author":"A Pirinen","year":"2019","unstructured":"Pirinen, A., Ames, B.: Exact clustering of weighted graphs via semidefinite programming. J. Mach. Learn. Res. 20(1), 1007\u20131040 (2019)","journal-title":"J. Mach. Learn. Res."},{"issue":"2","key":"1886_CR33","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0167-6377(96)00021-1","volume":"19","author":"A Tamir","year":"1996","unstructured":"Tamir, A.: An $${O}(pn^2)$$ algorithm for the $$p$$-median and related problems on tree graphs. Oper. Res. Lett. 19(2), 59\u201364 (1996)","journal-title":"Oper. Res. Lett."},{"key":"1886_CR34","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596","volume-title":"High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics","author":"R Vershynin","year":"2018","unstructured":"Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (2018)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01886-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01886-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01886-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,5]],"date-time":"2024-10-05T08:28:23Z","timestamp":1728116903000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01886-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,6]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1886"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01886-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2022,10,6]]},"assertion":[{"value":"6 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}