{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T06:48:48Z","timestamp":1774421328975,"version":"3.50.1"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031159138","type":"print"},{"value":"9783031159145","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-15914-5_16","type":"book-chapter","created":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T11:14:22Z","timestamp":1664536462000},"page":"215-229","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Generalized $$k$$-Center: Distinguishing Doubling and Highway Dimension"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6229-5332","authenticated-orcid":false,"given":"Andreas Emil","family":"Feldmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8902-5196","authenticated-orcid":false,"given":"Tung Anh","family":"Vu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,1]]},"reference":[{"issue":"5","key":"16_CR1","doi-asserted-by":"publisher","first-page":"1","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 (JACM) 63(5), 1\u201326 (2016)","journal-title":"J. ACM (JACM)"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension, shortest paths, and provably efficient algorithms. In: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pp. 782\u2013793. SIAM (2010)","DOI":"10.1137\/1.9781611973075.64"},{"key":"16_CR3","doi-asserted-by":"publisher","unstructured":"Ahmadi-Javid, A., Seyedi, P., Syam, S.S.: A survey of healthcare facility location. Comput. Oper. Res. 79, 223\u2013263 (2017). https:\/\/doi.org\/10.1016\/j.cor.2016.05.018, https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0305054816301253","DOI":"10.1016\/j.cor.2016.05.018"},{"issue":"1\u20132","key":"16_CR4","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s10107-014-0857-y","volume":"154","author":"HC An","year":"2015","unstructured":"An, H.C., 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). https:\/\/doi.org\/10.1007\/s10107-014-0857-y","journal-title":"Math. Program."},{"key":"16_CR5","unstructured":"Bast, H., Funke, S., Matijevic, D.: Transit ultrafast shortest-path queries with linear-time preprocessing. 9th DIMACS Implementation Challenge [1] (2006)"},{"key":"16_CR6","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: 2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 46\u201359. SIAM (2007)","DOI":"10.1137\/1.9781611972870.5"},{"key":"16_CR7","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). Leibniz International Proceedings in Informatics (LIPIcs), vol. 112, pp. 8:1\u20138:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018)"},{"key":"16_CR8","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). Leibniz International Proceedings in Informatics (LIPIcs), vol. 148, pp. 4:1\u20134:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019)"},{"key":"16_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-642-11269-0_4","volume-title":"Parameterized and Exact Computation","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Lokshtanov, D., Penninkx, E.: Planar capacitated dominating set is W[1]-Hard. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 50\u201360. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-11269-0_4"},{"key":"16_CR10","doi-asserted-by":"publisher","unstructured":"Chakrabarty, D., Goyal, P., Krishnaswamy, R.: The non-uniform k-center problem. ACM Trans. Algorithms 16(4) (2020). https:\/\/doi.org\/10.1145\/3392720","DOI":"10.1145\/3392720"},{"key":"16_CR11","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: SODA, vol. 1, pp. 642\u2013651 (2001)"},{"issue":"6","key":"16_CR12","doi-asserted-by":"publisher","first-page":"1","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), 1\u201334 (2021). https:\/\/doi.org\/10.1145\/3477541","journal-title":"J. ACM"},{"key":"16_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Cygan, M., Hajiaghayi, M., Khuller, S.: LP rounding for k-centers with non-uniform hard capacities. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 273\u2013282. IEEE (2012)","DOI":"10.1109\/FOCS.2012.63"},{"key":"16_CR15","doi-asserted-by":"publisher","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). Leibniz International Proceedings in Informatics (LIPIcs), vol. 25, pp. 251\u2013262. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2014). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2014.251, https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2014\/4462","DOI":"10.4230\/LIPIcs.STACS.2014.251"},{"key":"16_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-79723-4_9","volume-title":"Parameterized and Exact Computation","author":"M Dom","year":"2008","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 78\u201390. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-79723-4_9"},{"key":"16_CR17","doi-asserted-by":"publisher","unstructured":"Feder, T., Greene, D.: Optimal algorithms for approximate clustering. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 434\u2013444. STOC 1988, Association for Computing Machinery, New York, NY, USA (1988). https:\/\/doi.org\/10.1145\/62212.62255,https:\/\/doi.org\/10.1145\/62212.62255","DOI":"10.1145\/62212.62255,"},{"issue":"3","key":"16_CR18","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). https:\/\/doi.org\/10.1007\/s00453-018-0455-0","journal-title":"Algorithmica"},{"issue":"4","key":"16_CR19","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., Konemann, J., Post, I.: A (1+$$\\varepsilon $$)-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":"16_CR20","doi-asserted-by":"publisher","first-page":"146","DOI":"10.3390\/a13060146","volume":"13","author":"AE Feldmann","year":"2020","unstructured":"Feldmann, A.E., Karthik, C., 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":"16_CR21","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). https:\/\/doi.org\/10.1007\/s00453-020-00683-w","journal-title":"Algorithmica"},{"key":"16_CR22","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/j.jcss.2021.06.002, https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000021000647","DOI":"10.1016\/j.jcss.2021.06.002"},{"key":"16_CR23","unstructured":"Goyal, D., Jaiswal, R.: Tight FPT approximation for constrained k-center and k-supplier. CoRR abs\/2110.14242 (2021). https:\/\/arxiv.org\/abs\/2110.14242"},{"key":"16_CR24","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.: Bounded geometries, fractals, and low-distortion embeddings. In: 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings, pp. 534\u2013543. IEEE (2003)"},{"key":"16_CR25","doi-asserted-by":"publisher","unstructured":"Harris, D.G., Pensyl, T., Srinivasan, A., Trinh, K.: A lottery model for center-type problems with outliers. ACM Trans. Algorithms 15(3) (2019). https:\/\/doi.org\/10.1145\/3311953","DOI":"10.1145\/3311953"},{"issue":"2","key":"16_CR26","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":"16_CR27","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). https:\/\/doi.org\/10.1145\/5925.5933","journal-title":"J. ACM"},{"key":"16_CR28","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":"16_CR29","doi-asserted-by":"publisher","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pp. 281\u2013290. STOC 2004, Association for Computing Machinery, New York, NY, USA (2004). https:\/\/doi.org\/10.1145\/1007352.1007399","DOI":"10.1145\/1007352.1007399"},{"key":"16_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2013","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-662-04565-7"},{"key":"16_CR31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithmsd","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithmsd. Cambridge University Press, Cambridge (2011)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-15914-5_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T11:17:14Z","timestamp":1664536634000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-15914-5_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031159138","9783031159145"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-15914-5_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"T\u00fcbingen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"48","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo.inf.uni-tuebingen.de\/wg2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"96","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}