English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we study the hardness of the $k$-Center problem on inputs thatmodel transportation networks. For the problem, a graph $G=(V,E)$ with edgelengths and an integer $k$ are given and a center set $C\subseteq V$ needs tobe chosen such that $|C|\leq k$. The aim is to minimize the maximum distance ofany vertex in the graph to the closest center. This problem arises in manyapplications of logistics, and thus it is natural to consider inputs that modeltransportation networks. Such inputs are often assumed to be planar graphs, lowdoubling metrics, or bounded highway dimension graphs. For each of thesemodels, parameterized approximation algorithms have been shown to exist. Wecomplement these results by proving that the $k$-Center problem is W[1]-hard onplanar graphs of constant doubling dimension, where the parameter is thecombination of the number of centers $k$, the highway dimension $h$, and thepathwidth $p$. Moreover, under the Exponential Time Hypothesis there is no$f(k,p,h)\cdot n^{o(p+\sqrt{k+h})}$ time algorithm for any computable function$f$. Thus it is unlikely that the optimum solution to $k$-Center can be foundefficiently, even when assuming that the input graph abides to all of the abovemodels for transportation networks at once!  Additionally we give a simple parameterized $(1+\varepsilon)$-approximationalgorithm for inputs of doubling dimension $d$ with runtime$(k^k/\varepsilon^{O(kd)})\cdot n^{O(1)}$. This generalizes a previous result,which considered inputs in $D$-dimensional $L_q$ metrics.

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