2026-07-21T19:38:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12912 2024-03-06T10:51:04Z ddc:004 open_access

Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs Feldmann, Andreas Emil Saulpic, David Approximation Scheme Clustering Highway Dimension 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andreas Emil Feldmann and David Saulpic 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.46 urn:nbn:de:0030-drops-129129 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.46 eng https://creativecommons.org/licenses/by/3.0/legalcode