We study clustering problems such as k-Median, k-Means, and Facility Location in graphs of low highway dimension, which is a graph parameter modeling transportation networks. It was previously shown that approximation schemes for these problems exist, which either run in quasi-polynomial time (assuming constant highway dimension) [Feldmann et al. SICOMP 2018] or run in FPT time (parameterized by the number of clusters k, the highway dimension, and the approximation factor) [Becker et al. ESA 2018, Braverman et al. 2020]. In this paper we show that a polynomial-time approximation scheme (PTAS) exists (assuming constant highway dimension). We also show that the considered problems are NP-hard on graphs of highway dimension 1.
@InProceedings{feldmann_et_al:LIPIcs.ESA.2020.46, author = {Feldmann, Andreas Emil and Saulpic, David}, title = {{Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {46:1--46:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.46}, URN = {urn:nbn:de:0030-drops-129129}, doi = {10.4230/LIPIcs.ESA.2020.46}, annote = {Keywords: Approximation Scheme, Clustering, Highway Dimension} }
Feedback for Dagstuhl Publishing