Generalized $k$-Center: Distinguishing Doubling and Highway Dimension

Abstract

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.

36 pages, 3 figures. Published in Algorithmica. Extended abstract of the paper appeared in WG 2022

References in corpus (2)

• The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
• A $(1+\epsilon )$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs