  In the Multiple Allocation $k$-Hub Center (MA$k$HC), we are given a connected
edge-weighted graph $G$, sets of clients $\mathcal{C}$ and hub locations
$\mathcal{H}$, where ${V(G) = \mathcal{C} \cup \mathcal{H}}$, a set of demands
$\mathcal{D} \subseteq \mathcal{C}^2$ and a positive integer $k$. A solution is
a set of hubs $H \subseteq \mathcal{H}$ of size $k$ such that every demand
$(a,b)$ is satisfied by a path starting in $a$, going through some vertex of
$H$, and ending in $b$. The objective is to minimize the largest length of a
path. We show that finding a $(3-\epsilon)$-approximation is NP-hard already
for planar graphs. For arbitrary graphs, the approximation lower bound holds
even if we parameterize by $k$ and the value $r$ of an optimal solution. An
exact FPT algorithm is also unlikely when the parameter combines $k$ and
various graph widths, including pathwidth. To confront these hardness barriers,
we give a $(2+\epsilon)$-approximation algorithm parameterized by treewidth,
and, as a byproduct, for unweighted planar graphs, we give a
$(2+\epsilon)$-approximation algorithm parameterized by $k$ and $r$. Compared
to classical location problems, computing the length of a path depends on
non-local decisions. This turns standard dynamic programming algorithms
impractical, thus our algorithm approximates this length using only local
information. We hope these ideas find application in other problems with
similar cost structure.
