论文标题
广义$ k $ - 中心：区分加倍和高速公路维度
Generalized $k$-Center: Distinguishing Doubling and Highway Dimension
论文作者
论文摘要
我们考虑$ k $中心问题的概括性在低加倍和高速公路尺寸的图表中。对于带有异常值（CKSWO）问题的电容$ k $ -supplier，当参数为$ k $时，我们显示了有效的参数化近似方案（EPAS），离群值的数量和供应商集的倍数。另一方面，我们表明，对于CKSWO的电容$ k $中心问题，获得参数化的近似方案（PAS）为$ \ mathrm {w [1]} $ - 当参数为$ k $，而高速公路尺寸。这是一个问题的第一个已知示例，很难为高速公路维度获得PAS，同时又承认EPAS加倍维度。
We consider generalizations of the $k$-Center problem in graphs of low doubling and highway dimension. For the Capacitated $k$-Supplier with Outliers (CkSwO) problem, we show an efficient parameterized approximation scheme (EPAS) when the parameters are $k$, the number of outliers and the doubling dimension of the supplier set. On the other hand, we show that for the Capacitated $k$-Center problem, which is a special case of CkSwO, obtaining a parameterized approximation scheme (PAS) is $\mathrm{W[1]}$-hard when the parameters are $k$, and the highway dimension. This is the first known example of a problem for which it is hard to obtain a PAS for highway dimension, while simultaneously admitting an EPAS for doubling dimension.
