Generalized k-Center: Distinguishing Doubling and Highway Dimension
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10515264" target="_blank" >RIV/00216208:11320/25:10515264 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=OY9mUfgX5K" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=OY9mUfgX5K</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00453-025-01357-1" target="_blank" >10.1007/s00453-025-01357-1</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Generalized k-Center: Distinguishing Doubling and Highway Dimension
Popis výsledku v původním jazyce
We consider generalizations of the k-CENTER problem in graphs of low doubling and highway dimension. For the CAPACITATED k-SUPPLIER wITH OUTLIERS (CK-SwO) problem, we show an efficient parameterized approximation scheme (EPAS) when the parameters are k, the number of outliers and the doubling dimension of the graph induced by 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 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.
Název v anglickém jazyce
Generalized k-Center: Distinguishing Doubling and Highway Dimension
Popis výsledku anglicky
We consider generalizations of the k-CENTER problem in graphs of low doubling and highway dimension. For the CAPACITATED k-SUPPLIER wITH OUTLIERS (CK-SwO) problem, we show an efficient parameterized approximation scheme (EPAS) when the parameters are k, the number of outliers and the doubling dimension of the graph induced by 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 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.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/LL2406" target="_blank" >LL2406: Robustní proudové algoritmy versus adaptivní protivníci</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2025
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Algorithmica
ISSN
0178-4617
e-ISSN
1432-0541
Svazek periodika
88
Číslo periodika v rámci svazku
1
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
36
Strana od-do
12
Kód UT WoS článku
001633601800002
EID výsledku v databázi Scopus
2-s2.0-105024072964