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.
翻译:我们研究的是诸如k-Median、k-Means和设施位置等在低高速公路维度图中的问题,这是运输网络的图形参数模型,以前曾表明存在这些问题的近似计划,这些近似计划要么在半极时运行(假设固定高速公路维度)[Feldmann等人,SICOMP 2018],要么在FPT 时运行(以美元组数、高速公路维度和近似因数为参数)[Becker等人,ESA~2018,Braverman等人,2020]。我们在本文件中表明存在一个多球时近似计划(假设固定高速公路维度),我们还表明,所考虑的问题在高速公路维度图1上是坚硬的。