{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T16:15:47Z","timestamp":1770048947222,"version":"3.49.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T00:00:00Z","timestamp":1765152000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T00:00:00Z","timestamp":1765152000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["19-27871X"],"award-info":[{"award-number":["19-27871X"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["22-22997S"],"award-info":[{"award-number":["22-22997S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,2]]},"DOI":"10.1007\/s00453-025-01357-1","type":"journal-article","created":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T05:19:44Z","timestamp":1765171184000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Generalized $$k$$-Center: Distinguishing Doubling and Highway Dimension"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6229-5332","authenticated-orcid":false,"given":"Andreas Emil","family":"Feldmann","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8902-5196","authenticated-orcid":false,"given":"Tung Anh","family":"Vu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,8]]},"reference":[{"issue":"5","key":"1357_CR1","doi-asserted-by":"publisher","first-page":"41:!","DOI":"10.1145\/2985473","volume":"63","author":"I Abraham","year":"2016","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway Dimension and Provably Efficient Shortest Path Algorithms. Journal of the ACM (JACM) 63(5), 41:!-41:6 (2016)","journal-title":"Journal of the ACM (JACM)"},{"key":"1357_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.F.: Highway Dimension, Shortest Paths, and Provably Efficient Algorithms. In: Charikar, M. (ed.) Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010. pp. 782\u2013793. SIAM (2010)","DOI":"10.1137\/1.9781611973075.64"},{"key":"1357_CR3","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.cor.2016.05.018","volume":"79","author":"A Ahmadi-Javid","year":"2017","unstructured":"Ahmadi-Javid, A., Seyedi, P., Syam, S.S.: A survey of healthcare facility location. Computers & Operations Research 79, 223\u2013263 (2017)","journal-title":"Computers & Operations Research"},{"issue":"1\u20132","key":"1357_CR4","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s10107-014-0857-y","volume":"154","author":"H An","year":"2015","unstructured":"An, H., Bhaskara, A., Chekuri, C., Gupta, S., Madan, V., Svensson, O.: Centrality of trees for capacitated k-center. Math. Program. 154(1\u20132), 29\u201353 (2015)","journal-title":"Math. Program."},{"issue":"4","key":"1357_CR5","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1137\/130913328","volume":"45","author":"Y Bartal","year":"2016","unstructured":"Bartal, Y., Gottlieb, L., Krauthgamer, R.: The traveling salesman problem: Low-dimensionality implies a polynomial time approximation scheme. SIAM J. Comput. 45(4), 1563\u20131581 (2016)","journal-title":"SIAM J. Comput."},{"key":"1357_CR6","unstructured":"Bast, H., Funke, S., Matijevic, D.: Transit ultrafast shortest-path queries with linear-time preprocessing. 9th DIMACS Implementation Challenge (2006)"},{"key":"1357_CR7","doi-asserted-by":"crossref","unstructured":"Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In Transit to Constant Time Shortest-Path Queries in Road Networks. In: Proceedings of the Nine Workshop on Algorithm Engineering and Experiments, ALENEX 2007, New Orleans, Louisiana, USA, January 6, 2007. SIAM (2007)","DOI":"10.1137\/1.9781611972870.5"},{"key":"1357_CR8","unstructured":"Becker, A., Klein, P.N., Saulpic, D.: Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension. In: Azar, Y., Bast, H., Herman, G. (eds.) 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland. LIPIcs, vol.\u00a0112, pp. 8:1\u20138:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"1357_CR9","unstructured":"Blum, J.: Hierarchy of Transportation Network Parameters and Hardness Results. In: Jansen, B.M.P., Telle, J.A. (eds.) 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany. LIPIcs, vol.\u00a0148, pp. 4:1\u20134:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"1357_CR10","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Lokshtanov, D., Penninkx, E.: Planar Capacitated Dominating Set Is W[1]-Hard. In: Chen, J., Fomin, F.V. (eds.) Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers. Lecture Notes in Computer Science, vol.\u00a05917, pp. 50\u201360. Springer (2009)","DOI":"10.1007\/978-3-642-11269-0_4"},{"key":"1357_CR11","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Goyal, P., Krishnaswamy, R.: The Non-Uniform k-Center Problem. ACM Trans. Algorithms 16(4), 46:1\u201346:19 (2020)","DOI":"10.1145\/3392720"},{"key":"1357_CR12","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Kosaraju, S.R. (ed.) Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA. pp. 642\u2013651. ACM\/SIAM (2001)"},{"key":"1357_CR13","unstructured":"Chatterjee, K., Ibsen-Jensen, R., Pavlogiannis, A.: Optimal tree-decomposition balancing and reachability on low treewidth graphs. https:\/\/research-explorer.app.ist.ac.at\/record\/5427 (2014), accessed: 2021-05-13"},{"issue":"6","key":"1357_CR14","doi-asserted-by":"publisher","first-page":"44:!","DOI":"10.1145\/3477541","volume":"68","author":"V Cohen-Addad","year":"2021","unstructured":"Cohen-Addad, V., Feldmann, A.E., Saulpic, D.: Near-linear Time Approximation Schemes for Clustering in Doubling Metrics. J. ACM 68(6), 44:!-44:34 (2021)","journal-title":"J. ACM"},{"key":"1357_CR15","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"1357_CR16","doi-asserted-by":"crossref","unstructured":"Cygan, M., Hajiaghayi, M., Khuller, S.: LP Rounding for k-Centers with Non-uniform Hard Capacities . In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012. pp. 273\u2013282. IEEE Computer Society (2012)","DOI":"10.1109\/FOCS.2012.63"},{"key":"1357_CR17","unstructured":"Cygan, M., Kociumaka, T.: Constant Factor Approximation for Capacitated k-Center with Outliers . In: Mayr, E.W., Portier, N. (eds.) 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France. LIPIcs, vol.\u00a025, pp. 251\u2013262. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2014)"},{"key":"1357_CR18","doi-asserted-by":"crossref","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated Domination and Covering: A Parameterized Perspective. In: Grohe, M., Niedermeier, R. (eds.) Parameterized and Exact Computation, Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008. Proceedings. Lecture Notes in Computer Science, vol.\u00a05018, pp. 78\u201390. Springer (2008)","DOI":"10.1007\/978-3-540-79723-4_9"},{"issue":"2","key":"1357_CR19","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. ACM 19(2), 248\u2013264 (1972)","journal-title":"J. ACM"},{"key":"1357_CR20","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.H.: Optimal Algorithms for Approximate Clustering. In: Simon, J. (ed.) Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA. pp. 434\u2013444. ACM (1988)","DOI":"10.1145\/62212.62255"},{"issue":"3","key":"1357_CR21","doi-asserted-by":"publisher","first-page":"1031","DOI":"10.1007\/s00453-018-0455-0","volume":"81","author":"AE Feldmann","year":"2019","unstructured":"Feldmann, A.E.: Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs. Algorithmica 81(3), 1031\u20131052 (2019)","journal-title":"Algorithmica"},{"key":"1357_CR22","unstructured":"Feldmann, A.E., Filtser, A.: Highway Dimension: a Metric View, pp. 3267\u20133276"},{"issue":"4","key":"1357_CR23","doi-asserted-by":"publisher","first-page":"1667","DOI":"10.1137\/16M1067196","volume":"47","author":"AE Feldmann","year":"2018","unstructured":"Feldmann, A.E., Fung, W.S., K\u00f6nemann, J., Post, I.: A (1+$$\\epsilon $$)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs. SIAM J. Comput. 47(4), 1667\u20131704 (2018)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1357_CR24","doi-asserted-by":"publisher","first-page":"146","DOI":"10.3390\/a13060146","volume":"13","author":"AE Feldmann","year":"2020","unstructured":"Feldmann, A.E., Karthik, C.S., Lee, E., Manurangsi, P.: A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Algorithms 13(6), 146 (2020)","journal-title":"Algorithms"},{"issue":"7","key":"1357_CR25","doi-asserted-by":"publisher","first-page":"1989","DOI":"10.1007\/s00453-020-00683-w","volume":"82","author":"AE Feldmann","year":"2020","unstructured":"Feldmann, A.E., Marx, D.: The Parameterized Hardness of the k-Center Problem in Transportation Networks. Algorithmica 82(7), 1989\u20132005 (2020)","journal-title":"Algorithmica"},{"key":"1357_CR26","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.jcss.2021.06.002","volume":"122","author":"AE Feldmann","year":"2021","unstructured":"Feldmann, A.E., Saulpic, D.: Polynomial time approximation schemes for clustering in low highway dimension graphs. J. Comput. Syst. Sci. 122, 72\u201393 (2021)","journal-title":"J. Comput. Syst. Sci."},{"key":"1357_CR27","doi-asserted-by":"crossref","unstructured":"Goyal, D., Jaiswal, R.: Tight FPT approximation for constrained k-center and k-supplier. Theor. Comput. Sci. 940(Part), 190\u2013208 (2023)","DOI":"10.1016\/j.tcs.2022.11.001"},{"key":"1357_CR28","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded Geometries, Fractals, and Low-Distortion Embeddings. In: 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings. pp. 534\u2013543. IEEE Computer Society (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"issue":"3","key":"1357_CR29","doi-asserted-by":"publisher","first-page":"36:1","DOI":"10.1145\/3311953","volume":"15","author":"DG Harris","year":"2019","unstructured":"Harris, D.G., Pensyl, T.W., Srinivasan, A., Trinh, K.: A Lottery Model for Center-Type Problems With Outliers. ACM Trans. Algorithms 15(3), 36:1-36:25 (2019)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"1357_CR30","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":"1357_CR31","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 33(3), 533\u2013550 (1986)","journal-title":"J. ACM"},{"key":"1357_CR32","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.dam.2018.11.002","volume":"264","author":"I Katsikarelis","year":"2019","unstructured":"Katsikarelis, I., Lampis, M., Paschos, V.T.: Structural parameters, tight bounds, and approximation for (k, r)-center. Discret. Appl. Math. 264, 90\u2013117 (2019)","journal-title":"Discret. Appl. Math."},{"key":"1357_CR33","unstructured":"Lampis, M.: Parameterized Approximation Schemes Using Graph Widths. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. Lecture Notes in Computer Science, vol.\u00a08572, pp. 775\u2013786. Springer (2014)"},{"key":"1357_CR34","doi-asserted-by":"crossref","unstructured":"Talwar, K.: Bypassing the Embedding: Algorithms for Low Dimensional Metrics. In: Babai, L. (ed.) Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004. pp. 281\u2013290. ACM (2004)","DOI":"10.1145\/1007352.1007399"},{"key":"1357_CR35","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer (2001)"},{"key":"1357_CR36","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511921735"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01357-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01357-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01357-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T05:12:07Z","timestamp":1770009127000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01357-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,8]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["1357"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01357-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,8]]},"assertion":[{"value":"15 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 December 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"We acknowledge that all authors agreed to submit the manuscript without any conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"12"}}