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.
翻译：本文研究在低倍增维度和低公路维度图中广义$k$-中心问题的计算复杂性。对于带离群点的容量约束$k$供应商问题（CkSwO），我们证明当参数为供应商集的倍增维度、设施数量$k$及离群点数量时，存在高效参数化近似方案（EPAS）。另一方面，对于作为CkSwO特例的容量约束$k$-中心问题，我们证明当参数为公路维度和$k$时，获得参数化近似方案（PAS）是$\mathrm{W[1]}$-困难的。这是首个已知的、在公路维度参数下难以获得PAS，同时在倍增维度参数下却允许EPAS的问题实例。
相关内容
微信扫码咨询专知VIP会员