{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:45:12Z","timestamp":1762299912560,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["263317"],"award-info":[{"award-number":["263317"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Non-Uniform <jats:italic>k<\/jats:italic>-center (NUkC) problem has recently been formulated by Chakrabarty et al. [ICALP, 2016; ACM Trans Algorithms 16(4):46:1\u201346:19, 2020] as a generalization of the classical <jats:italic>k<\/jats:italic>-center clustering problem. In NUkC, given a set of <jats:italic>n<\/jats:italic> points <jats:italic>P<\/jats:italic> in a metric space and non-negative numbers <jats:inline-formula><jats:alternatives><jats:tex-math>$$r_1, r_2, \\ldots , r_k$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:msub>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msub>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u2026<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the goal is to find the minimum dilation <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\alpha $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b1<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and to choose <jats:italic>k<\/jats:italic> balls centered at the points of <jats:italic>P<\/jats:italic> with radius <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\alpha \\cdot r_i$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b1<\/mml:mi>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mi>i<\/mml:mi>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for <jats:inline-formula><jats:alternatives><jats:tex-math>$$1\\le i\\le k$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mi>i<\/mml:mi>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, such that all points of <jats:italic>P<\/jats:italic> are contained in the union of the chosen balls. They showed that the problem is <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard to approximate within any factor even in tree metrics. On the other hand, they designed a \u201cbi-criteria\u201d constant approximation algorithm that uses a constant times <jats:italic>k<\/jats:italic> balls. Surprisingly, no true approximation is known even in the special case when the <jats:inline-formula><jats:alternatives><jats:tex-math>$$r_i$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mi>i<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u2019s belong to a fixed set of size 3. In this paper, we study the NUkC problem under perturbation resilience, which was introduced by Bilu and Linial (Comb Probab Comput 21(5):643\u2013660, 2012). We show that the problem under 2-perturbation resilience is polynomial time solvable when the <jats:inline-formula><jats:alternatives><jats:tex-math>$$r_i$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mi>i<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u2019s belong to a constant-sized set. However, we show that perturbation resilience does not help in the general case. In particular, our findings imply that even with perturbation resilience one cannot hope to find any \u201cgood\u201d approximation for the problem.<\/jats:p>","DOI":"10.1007\/s00453-021-00887-8","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T14:02:42Z","timestamp":1635429762000},"page":"13-36","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Perturbation Resilience of Non-uniform k-Center"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8875-0102","authenticated-orcid":false,"given":"Sayan","family":"Bandyapadhyay","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,28]]},"reference":[{"key":"887_CR1","doi-asserted-by":"crossref","unstructured":"Adjiashvili, D., Baggio, A., Zenklusen, R.: Firefighting on trees beyond integrality gaps. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, pp. 2364\u20132383 (2017)","DOI":"10.1137\/1.9781611974782.156"},{"key":"887_CR2","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.tcs.2015.04.030","volume":"588","author":"M Agarwal","year":"2015","unstructured":"Agarwal, M., Jaiswal, R., Pal, A.: $$k$$-means++ under approximation stability. Theor. Comput. Sci. 588, 37\u201351 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"887_CR3","doi-asserted-by":"crossref","unstructured":"Ahmadian, S., Norouzi-Fard, A., Svensson, O., Ward, J.: Better guarantees for $$k$$-means and Euclidean $$k$$-median by primal\u2013dual algorithms. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, pp. 61\u201372 (2017)","DOI":"10.1109\/FOCS.2017.15"},{"key":"887_CR4","doi-asserted-by":"crossref","unstructured":"Angelidakis, H., Makarychev, K., Makarychev, Y.: Algorithms for stable and perturbation-resilient problems. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, pp. 438\u2013451 (2017)","DOI":"10.1145\/3055399.3055487"},{"key":"887_CR5","doi-asserted-by":"crossref","unstructured":"Awasthi, P., Blum, A., Sheffet, O.: Stability yields a PTAS for $$k$$-median and $$k$$-means clustering. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23\u201326, 2010, Las Vegas, Nevada, USA, pp. 309\u2013318 (2010)","DOI":"10.1109\/FOCS.2010.36"},{"issue":"1\u20132","key":"887_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. 112(1\u20132), 49\u201354 (2012)","journal-title":"Inf. Process. Lett."},{"key":"887_CR7","unstructured":"Balcan, M.-F., Haghtalab, N., White, C.: $$k$$-center clustering under perturbation resilience. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, pp. 68:1\u201368:14 (2016)"},{"issue":"1","key":"887_CR8","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1137\/140981575","volume":"45","author":"M-F Balcan","year":"2016","unstructured":"Balcan, M.-F., Liang, Y.: Clustering under perturbation resilience. SIAM J. Comput. 45(1), 102\u2013155 (2016)","journal-title":"SIAM J. Comput."},{"key":"887_CR9","unstructured":"Bandyapadhyay, S., Varadarajan, K.R.: Approximate clustering via metric partitioning. In: 27th International Symposium on Algorithms and Computation, ISAAC 2016, Sydney, Australia, pp. 15:1\u201315:13 (2016)"},{"issue":"5","key":"887_CR10","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1017\/S0963548312000193","volume":"21","author":"Y Bilu","year":"2012","unstructured":"Bilu, Y., Linial, N.: Are stable instances easy? Comb. Probab. Comput. 21(5), 643\u2013660 (2012)","journal-title":"Comb. Probab. Comput."},{"key":"887_CR11","unstructured":"Bura, V.: A kernel method for positive 1-in-3-sat (2018). CoRR, arXiv:1808.02821"},{"issue":"2","key":"887_CR12","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/2981561","volume":"13","author":"J Byrka","year":"2017","unstructured":"Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for k-median and positive correlation in budgeted optimization. ACM Trans. Algorithms 13(2), 23:1-23:31 (2017)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"887_CR13","doi-asserted-by":"publisher","first-page":"46:1","DOI":"10.1145\/3392720","volume":"16","author":"D Chakrabarty","year":"2020","unstructured":"Chakrabarty, D., Goyal, P., Krishnaswamy, R.: The non-uniform k-center problem. ACM Trans. Algorithms 16(4), 46:1-46:19 (2020)","journal-title":"ACM Trans. Algorithms"},{"key":"887_CR14","unstructured":"Chekuri, C., Gupta, S.: Perturbation resilient clustering for $$k$$-center and related problems via LP relaxations. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2018\u2014Princeton, NJ, USA, pp. 9:1\u20139:16 (2018)"},{"issue":"4","key":"887_CR15","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/1082036.1082038","volume":"52","author":"J Chuzhoy","year":"2005","unstructured":"Chuzhoy, J., Guha, S., Halperin, E., Khanna, S., Kortsarz, G., Krauthgamer, R., Naor, J.: Asymmetric k-center is log$${}^{*}\\mathit{n}$$-hard to approximate. J. ACM 52(4), 538\u2013551 (2005)","journal-title":"J. ACM"},{"key":"887_CR16","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V., Schwiegelshohn, C.: On the local structure of stable clustering instances. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 2017, pp. 49\u201360 (2017)","DOI":"10.1109\/FOCS.2017.14"},{"key":"887_CR17","unstructured":"Deshpande, A., Louis, A., Singh, A.: On Euclidean $$k$$-means clustering with alpha-center proximity. In: Chaudhuri, K., Sugiyama, M., (eds.), Proceedings of Machine Learning Research, Volume 89 of Proceedings of Machine Learning Research, pp. 2087\u20132095. PMLR, 16\u201318 April 2019"},{"issue":"16","key":"887_CR18","doi-asserted-by":"publisher","first-page":"2094","DOI":"10.1016\/j.disc.2005.12.053","volume":"307","author":"S Finbow","year":"2007","unstructured":"Finbow, S., King, A.D., MacGillivray, G., Rizzi, R.: The firefighter problem for graphs of maximum degree three. Discrete Math. 307(16), 2094\u20132105 (2007)","journal-title":"Discrete Math."},{"key":"887_CR19","doi-asserted-by":"crossref","unstructured":"Friggstad, Z., Khodamoradi, K., Salavatipour, M.R.: Exact algorithms and lower bounds for stable instances of Euclidean $$k$$-means. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6\u20139, 2019, pp. 2958\u20132972 (2019)","DOI":"10.1137\/1.9781611975482.183"},{"key":"887_CR20","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"887_CR21","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s004540010020","volume":"24","author":"A Gupta","year":"2000","unstructured":"Gupta, A.: Embedding tree metrics into low-dimensional Euclidean spaces. Discrete Comput. Geom. 24(1), 105\u2013116 (2000)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"887_CR22","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.10.2.180","volume":"10","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the k-center problem. Math. Oper. Res. 10(2), 180\u2013184 (1985)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"887_CR23","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1016\/j.disc.2009.05.007","volume":"310","author":"AD King","year":"2010","unstructured":"King, A.D., MacGillivray, G.: The firefighter problem for cubic graphs. Discrete Math. 310(3), 614\u2013621 (2010)","journal-title":"Discrete Math."},{"key":"887_CR24","doi-asserted-by":"crossref","unstructured":"Kumar, A., Kannan, R.: Clustering with spectral norm and the $$k$$-means algorithm. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, Nevada, USA, pp. 299\u2013308 (2010)","DOI":"10.1109\/FOCS.2010.35"},{"key":"887_CR25","doi-asserted-by":"crossref","unstructured":"Makarychev, K., Makarychev, Y., Vijayaraghavan, A.: Bilu\u2013Linial stable instances of max cut and minimum multiway cut. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, pp. 890\u2013906 (2014)","DOI":"10.1137\/1.9781611973402.67"},{"key":"887_CR26","doi-asserted-by":"crossref","unstructured":"Mihal\u00e1k, M., Sch\u00f6ngens, M., Sr\u00e1mek, R., Widmayer, P.: On the complexity of the metric TSP under stability considerations. In: Proceedings of 37th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011: Theory and Practice of Computer Science, Nov\u00fd Smokovec, Slovakia, pp. 382\u2013393 (2011)","DOI":"10.1007\/978-3-642-18381-2_32"},{"issue":"6","key":"887_CR27","doi-asserted-by":"publisher","first-page":"28:1","DOI":"10.1145\/2395116.2395117","volume":"59","author":"R Ostrovsky","year":"2012","unstructured":"Ostrovsky, R., Rabani, Y., Schulman, L.J., Swamy, C.: The effectiveness of Lloyd-type methods for the $$k$$-means problem. J. ACM 59(6), 28:1-28:22 (2012)","journal-title":"J. ACM"},{"key":"887_CR28","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, STOC 1978, San Diego, California, USA, pp. 216\u2013226. ACM (1978)","DOI":"10.1145\/800133.804350"},{"key":"887_CR29","doi-asserted-by":"crossref","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. In: Proceedings of the 17th Annual ACM Symposium on Theory of Computing, STOC 1985, pp. 458\u2013463. ACM (1985)","DOI":"10.1145\/22145.22196"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00887-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00887-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00887-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T14:06:21Z","timestamp":1643033181000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00887-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,28]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["887"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00887-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,10,28]]},"assertion":[{"value":"31 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}