Polynomial time approximation schemes for clustering in low highway dimension graphs

摘要

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., 2018) [8] or run in FPT time (parameterized by the number of clusters k, the highway dimension, and the approximation factor) (Becker et al., 2018; Braverman et al., 2021) [9], [10]. 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.