The Parameterized Hardness of the k-Center Problem in Transportation Networks

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10387192" target="_blank" >RIV/00216208:11320/18:10387192 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.4230/LIPIcs.SWAT.2018.19" target="_blank" >https://doi.org/10.4230/LIPIcs.SWAT.2018.19</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.SWAT.2018.19" target="_blank" >10.4230/LIPIcs.SWAT.2018.19</a>

Jazyk výsledku

angličtina

Název v původním jazyce

The Parameterized Hardness of the k-Center Problem in Transportation Networks

Popis výsledku v původním jazyce

In this paper we study the hardness of the k-Center problem on inputs that model transportation networks. For the problem, an edge-weighted graph G=(V,E) and an integer k are given and a center set C subseteq V needs to be chosen such that |C|&lt;= k. The aim is to minimize the maximum distance of any vertex in the graph to the closest center. This problem arises in many applications of logistics, and thus it is natural to consider inputs that model transportation networks. Such inputs are often assumed to be planar graphs, low doubling metrics, or bounded highway dimension graphs. For each of these models, parameterized approximation algorithms have been shown to exist. We complement these results by proving that the k-Center problem is W[1]-hard on planar graphs of constant doubling dimension, where the parameter is the combination of the number of centers k, the highway dimension h, and even the treewidth t.

Název v anglickém jazyce

The Parameterized Hardness of the k-Center Problem in Transportation Networks

Popis výsledku anglicky

In this paper we study the hardness of the k-Center problem on inputs that model transportation networks. For the problem, an edge-weighted graph G=(V,E) and an integer k are given and a center set C subseteq V needs to be chosen such that |C|&lt;= k. The aim is to minimize the maximum distance of any vertex in the graph to the closest center. This problem arises in many applications of logistics, and thus it is natural to consider inputs that model transportation networks. Such inputs are often assumed to be planar graphs, low doubling metrics, or bounded highway dimension graphs. For each of these models, parameterized approximation algorithms have been shown to exist. We complement these results by proving that the k-Center problem is W[1]-hard on planar graphs of constant doubling dimension, where the parameter is the combination of the number of centers k, the highway dimension h, and even the treewidth t.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

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ů

Název statě ve sborníku

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

ISBN

978-3-95977-068-2

ISSN

1868-8969

e-ISSN

neuvedeno

Počet stran výsledku

13

Strana od-do

1-13

Název nakladatele

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Místo vydání

Dagstuhl, Germany

Místo konání akce

Malmö, Švédsko

Datum konání akce

18. 6. 2018

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—