论文标题
在低公路维度图中聚类的多项式时间近似方案
Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs
论文作者
论文摘要
我们研究了诸如K-Median，K-均值和设施位置之类的聚类问题，该图是低公路维度的图形，这是一个图参数建模运输网络。以前表明，存在这些问题的近似方案，要么以准多项式时间（假设恒定高速公路维度）运行[Feldmann等。 SICOMP 2018]或以FPT时间运行（由$ k $，高速公路维度和近似因子的群集数量进行参数化）[Becker等。 ESA〜2018，Braverman等。 2020]。在本文中，我们表明存在多项式时间近似方案（PTA）（假设恒定高速公路维度）。我们还表明，所考虑的问题是公路维度1的图表上的NP- hard。
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.
