Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2209.00675 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918259738017792 |
|---|---|
| author | Feldmann, Andreas Emil Vu, Tung Anh |
| author_facet | Feldmann, Andreas Emil Vu, Tung Anh |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_00675 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Generalized $k$-Center: Distinguishing Doubling and Highway Dimension Feldmann, Andreas Emil Vu, Tung Anh Data Structures and Algorithms 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. |
| title | Generalized $k$-Center: Distinguishing Doubling and Highway Dimension |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2209.00675 |