{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:50:07Z","timestamp":1781077807158,"version":"3.54.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,2,3]],"date-time":"2020-02-03T00:00:00Z","timestamp":1580688000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,3]],"date-time":"2020-02-03T00:00:00Z","timestamp":1580688000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["725978"],"award-info":[{"award-number":["725978"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"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\/100007397","name":"Univerzita Karlova v Praze","doi-asserted-by":"publisher","award":["UNCE\/SCI\/004"],"award-info":[{"award-number":["UNCE\/SCI\/004"]}],"id":[{"id":"10.13039\/100007397","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s00453-020-00683-w","type":"journal-article","created":{"date-parts":[[2020,2,3]],"date-time":"2020-02-03T07:02:33Z","timestamp":1580713353000},"page":"1989-2005","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["The Parameterized Hardness of the k-Center Problem in Transportation Networks"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6229-5332","authenticated-orcid":false,"given":"Andreas Emil","family":"Feldmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,2,3]]},"reference":[{"key":"683_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension, shortest paths, and provably efficient algorithms. In: SODA, pp. 782\u2013793 (2010)","DOI":"10.1137\/1.9781611973075.64"},{"key":"683_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: VC-dimension and shortest path algorithms. In: ICALP, pp. 690\u2013699 (2011)","DOI":"10.1007\/978-3-642-22006-7_58"},{"issue":"5","key":"683_CR3","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. J. ACM 63(5), 41 (2016)","journal-title":"J. ACM"},{"issue":"2","key":"683_CR4","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":"683_CR5","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: ALENEX, pp. 46\u201359 (2007)","DOI":"10.1137\/1.9781611972870.5"},{"key":"683_CR6","doi-asserted-by":"crossref","unstructured":"Bast, H., Funke, S., Matijevic, D.: Ultrafast shortest-path queries via transit nodes. In: 9th DIMACS Implementation Challenge, vol. 74, pp. 175\u2013192 (2009)","DOI":"10.1090\/dimacs\/074\/07"},{"key":"683_CR7","unstructured":"Becker, A., Klein, P.N., Saulpic, D.: Polynomial-time approximation schemes for $$k$$-center and bounded-capacity vehicle routing in metrics with bounded highway dimension. In: ESA, pp. 8:1\u20138:15 (2018)"},{"key":"683_CR8","unstructured":"Blum, J.: Hierarchy of transportation network parameters and hardness results. In: IPEC, pp. 4:1\u20134:15 (2019)"},{"key":"683_CR9","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. Springer, Berlin (2015)"},{"issue":"1","key":"683_CR10","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1077464.1077468","volume":"1","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Fixed-parameter algorithms for $$(k, r)$$-center in planar graphs and map graphs. Trans. Algorithms 1(1), 33\u201347 (2005)","journal-title":"Trans. Algorithms"},{"key":"683_CR11","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: STOC (2014)","DOI":"10.1145\/2591796.2591884"},{"key":"683_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)"},{"key":"683_CR13","doi-asserted-by":"crossref","unstructured":"Eisenstat, D., Klein, P.N., Mathieu, C.: Approximating $$k$$-center in planar graphs. In: SODA, pp. 617\u2013627 (2014)","DOI":"10.1137\/1.9781611973402.47"},{"key":"683_CR14","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.: Optimal algorithms for approximate clustering. In: STOC, pp. 434\u2013444 (1988)","DOI":"10.1145\/62212.62255"},{"issue":"3","key":"683_CR15","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":"683_CR16","unstructured":"Feldmann, A.E., Marx, D.: The parameterized hardness of the k-center problem in transportation networks. In: SWAT, pp. 19:1\u201319:13 (2018)"},{"issue":"4","key":"683_CR17","doi-asserted-by":"publisher","first-page":"1275","DOI":"10.1137\/15M102695X","volume":"47","author":"AE Feldmann","year":"2018","unstructured":"Feldmann, A.E., Fung, W.S., K\u00f6nemann, J., Post, I.: A $$(1+\\varepsilon )$$-embedding of low highway dimension graphs into bounded treewidth graphs. SIAM J. Comput. 47(4), 1275\u20131734 (2018)","journal-title":"SIAM J. Comput."},{"key":"683_CR18","doi-asserted-by":"crossref","unstructured":"Fox-Epstein, E., Klein, P.N., Schild, A.: Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems. In: SODA, pp. 1069\u20131088 (2019)","DOI":"10.1137\/1.9781611975482.66"},{"key":"683_CR19","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: FOCS, pp. 534\u2013543 (2003)"},{"issue":"3","key":"683_CR20","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"},{"issue":"5","key":"683_CR21","first-page":"33:1","volume":"66","author":"CS Karthik","year":"2019","unstructured":"Karthik, C.S., Laekhanukit, B., Manurangsi, P.: On the parameterized complexity of approximating dominating set. J. ACM 66(5), 33:1\u201333:38 (2019)","journal-title":"J. ACM"},{"key":"683_CR22","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, VTh: Structural parameters, tight bounds, and approximation for $$(k, r)$$-center. Discrete Appl. Math. 264, 90\u2013117 (2019)","journal-title":"Discrete Appl. Math."},{"key":"683_CR23","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Panolan, F., Ramanujan, M.S., Saurabh, S.: Lossy kernelization. In: STOC, pp. 224\u2013237 (2017)","DOI":"10.1145\/3055399.3055456"},{"key":"683_CR24","doi-asserted-by":"crossref","unstructured":"Marx, D.: Efficient approximation schemes for geometric problems? In: ESA, pp. 448\u2013459 (2005)","DOI":"10.1007\/11561071_41"},{"issue":"1","key":"683_CR25","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51(1), 60\u201378 (2008)","journal-title":"Comput. J."},{"key":"683_CR26","doi-asserted-by":"crossref","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In: ESA, pp. 865\u2013877 (2015)","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"683_CR27","doi-asserted-by":"crossref","unstructured":"Marx, D., Sidiropoulos, A.: The limited blessing of low dimensionality: when $$1-1\/d$$ is the best possible exponent for $$d$$-dimensional geometric problems. In: SOCG, p. 67 (2014)","DOI":"10.1145\/2582112.2582124"},{"issue":"6","key":"683_CR28","first-page":"445","volume":"25","author":"J Plesn\u00edk","year":"1980","unstructured":"Plesn\u00edk, J.: On the computational complexity of centers locating in a graph. Aplikace matematiky 25(6), 445\u2013452 (1980)","journal-title":"Aplikace matematiky"},{"key":"683_CR29","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, New York (2001)"},{"key":"683_CR30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00683-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00683-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00683-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,2]],"date-time":"2021-02-02T00:13:53Z","timestamp":1612224833000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00683-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,3]]},"references-count":30,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["683"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00683-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,3]]},"assertion":[{"value":"22 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}