Capacitated k-Center in Low Doubling and Highway Dimension

We consider the Capacitated k-Center problem, which is an \(\mathsf{APX}\)-hard problem. In order to achieve a \(\mathsf{PTAS}\), we consider graph parameters doubling and highway dimension. The former generalizes \(d\)-dimensional \(l_q\) metric spaces, the latter captures properties of transportation networks. In low doubling dimension graphs we achieve an efficient parameterized approximation scheme (\(\mathsf{EPAS}\)). On the other hand, we show a hardness of parameterized approximation result for low highway dimension graphs.