{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T15:10:34Z","timestamp":1721920234255},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T00:00:00Z","timestamp":1715558400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T00:00:00Z","timestamp":1715558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,8]]},"DOI":"10.1007\/s00453-024-01236-1","type":"journal-article","created":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T19:01:31Z","timestamp":1715626891000},"page":"2557-2574","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Approximation Algorithms and Lower Bounds for k-Center Clustering and Variants"],"prefix":"10.1007","volume":"86","author":[{"given":"Sayan","family":"Bandyapadhyay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zachary","family":"Friggstad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramin","family":"Mousavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,13]]},"reference":[{"issue":"2","key":"1236_CR1","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s00453-001-0110-y","volume":"33","author":"PK Agarwal","year":"2002","unstructured":"Agarwal, P.K., Procopiuc, C.M.: Exact and approximation algorithms for clustering. Algorithmica 33(2), 201\u2013226 (2002)","journal-title":"Algorithmica"},{"key":"1236_CR2","unstructured":"Awasthi, P., Charikar, M., Krishnaswamy, R., Sinop, A.\u00a0K. The hardness of approximation of euclidean k-means. arXiv preprint arXiv:1502.03316 (2015)"},{"key":"1236_CR3","unstructured":"Badoiu, M., Clarkson, K.\u00a0L.: Smaller core-sets for balls. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, Maryland. ACM\/SIAM, pp.\u00a0801\u2013802 (2003)"},{"key":"1236_CR4","doi-asserted-by":"crossref","unstructured":"Badoiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proceedings on 34th Annual ACM Symposium on Theory of Computing. Montr\u00e9al, Qu\u00e9bec, Canada, J.\u00a0H. Reif, Ed., ACM, pp.\u00a0250\u2013257 (2002)","DOI":"10.1145\/509907.509947"},{"key":"1236_CR5","unstructured":"Bandyapadhyay, S.: On perturbation resilience of non-uniform k-center. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"1236_CR6","unstructured":"Bhattacharya, A., Goyal, D., Jaiswal, R.: Hardness of approximation of euclidean $$ k $$-median. arXiv preprint arXiv:2011.04221 (2020)"},{"key":"1236_CR7","unstructured":"Bhattiprolu, V. V. S.\u00a0P., Har-Peled, S.: Separating a voronoi diagram via local search. In: 32nd International Symposium on Computational Geometry (SoCG 2016). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"issue":"4","key":"1236_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2000807.2000811","volume":"7","author":"S Cabello","year":"2011","unstructured":"Cabello, S., Giannopoulos, P., Knauer, C., Marx, D., Rote, G.: Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension. ACM Trans. Algorithms (TALG) 7(4), 1\u201327 (2011)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"4","key":"1236_CR9","doi-asserted-by":"publisher","first-page":"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 (TALG) 16(4), 1\u201319 (2020)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"1236_CR10","unstructured":"Chen, R.: On Mentzer\u2019s hardness of the k-center problem on the Euclidean plane"},{"key":"1236_CR11","unstructured":"Chitnis, R., Saurabh, N.: Tight lower bounds for approximate & exact k-center in $${\\mathbb{R}}^d$$. In: 38th International Symposium on Computational Geometry (SoCG 2022), Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"1236_CR12","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V.: A fast approximation scheme for low-dimensional k-means. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, 2018, A.\u00a0Czumaj, Ed., SIAM, pp.\u00a0430\u2013440 (2018)","DOI":"10.1137\/1.9781611975031.29"},{"key":"1236_CR13","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V., Lee, E.: Johnson coverage hypothesis: Inapproximability of k-means and k-median in lp-metrics. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, pp.\u00a01493\u20131530 (2022)","DOI":"10.1137\/1.9781611977073.63"},{"key":"1236_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, vol. 5. Springer, Berlin (2015)"},{"key":"1236_CR15","doi-asserted-by":"crossref","unstructured":"de\u00a0Berg, M., Bodlaender, H.\u00a0L., Kisfaludi-Bak, S., Marx, D., Zanden, T. C. V.\u00a0d.: A framework for eth-tight algorithms and lower bounds in geometric intersection graphs. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp.\u00a0574\u2013586 (2018)","DOI":"10.1145\/3188745.3188854"},{"key":"1236_CR16","doi-asserted-by":"crossref","unstructured":"De\u00a0La\u00a0Vega, W.\u00a0F., Karpinski, M., Kenyon, C., Rabani, Y.: Approximation schemes for clustering problems. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp.\u00a050\u201358 (2003)","DOI":"10.1145\/780542.780550"},{"issue":"4","key":"1236_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2635812","volume":"10","author":"H Dell","year":"2014","unstructured":"Dell, H., Husfeldt, T., Marx, D., Taslaman, N., Wahl\u00e9n, M.: Exponential time complexity of the permanent and the tutte polynomial. ACM Trans. Algorithms (TALG) 10(4), 1\u201332 (2014)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"1236_CR18","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.: Optimal algorithms for approximate clustering. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp.\u00a0434\u2013444 (1988)","DOI":"10.1145\/62212.62255"},{"key":"1236_CR19","unstructured":"Goel, A., Indyk, P., Varadarajan, K.\u00a0R.: Reductions among high dimensional proximity problems. In: Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001, Washington, DC, USA, S.\u00a0R. Kosaraju, Ed., ACM\/SIAM, pp.\u00a0769\u2013778 (2001)"},{"key":"1236_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."},{"key":"1236_CR21","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing , pp.\u00a0291\u2013300 (2004)","DOI":"10.1145\/1007352.1007400"},{"issue":"3","key":"1236_CR22","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"DS Hochbaum","year":"1986","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A unified approach to approximation algorithms for bottleneck problems. J ACM (JACM) 33(3), 533\u2013550 (1986)","journal-title":"J ACM (JACM)"},{"issue":"4","key":"1236_CR23","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"1236_CR24","doi-asserted-by":"crossref","unstructured":"Jansen, B.: Kernelization for maximum leaf spanning tree with positive vertex weights. In: International Conference on Algorithms and Complexity. Springer, pp.\u00a0192\u2013203 (2010)","DOI":"10.1007\/978-3-642-13073-1_18"},{"key":"1236_CR25","doi-asserted-by":"crossref","unstructured":"Johnson, W.\u00a0B., Lindenstrauss, J.: Extensions of lipschitz mappings into a hilbert space 26. In: Contemporary Mathematics 26 (1984)","DOI":"10.1090\/conm\/026\/737400"},{"issue":"2","key":"1236_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1667053.1667054","volume":"57","author":"A Kumar","year":"2010","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: Linear-time approximation schemes for clustering problems in any dimensions. J. ACM 57(2), 1\u201332 (2010)","journal-title":"J. ACM"},{"key":"1236_CR27","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2010.05.034","volume":"442","author":"M Mahajan","year":"2012","unstructured":"Mahajan, M., Nimbhorkar, P., Varadarajan, K.R.: The planar k-means problem is np-hard. Theor. Comput. Sci. 442, 13\u201321 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1236_CR28","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N., Supowit, K.J.: On the complexity of some common geometric location problems. SIAM J. Comput. 13(1), 182\u2013196 (1984)","journal-title":"SIAM J. Comput."},{"key":"1236_CR29","unstructured":"Mentzer, S.\u00a0G.: Approximability of metric clustering problems. Manuscript https:\/\/www.academia.edu\/23251714 Approximability of Metric Clustering Problems (1988)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01236-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01236-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01236-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T14:39:21Z","timestamp":1721918361000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01236-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,13]]},"references-count":29,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["1236"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01236-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,13]]},"assertion":[{"value":"4 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare, financial or otherwise.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}