2015 | OriginalPaper | Buchkapitel
Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
verfasst von : Dániel Marx, Michał Pilipczuk
Erschienen in: Algorithms - ESA 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study a general family of facility location problems defined on planar graphs and on the 2-dimensional plane. In these problems, a subset of
k
objects has to be selected, satisfying certain packing (disjointness) and covering constraints. Our main result is showing that, for each of these problems, the
$n^{{\mathcal{O}}(k)}$
time brute force algorithm of selecting
k
objects can be improved to
$n^{{\mathcal{O}}(\sqrt{k})}$
time. The algorithm is based on focusing on the Voronoi diagram of a hypothetical solution of
k
objects; this idea was introduced recently in the design of geometric QPTASs, but was not yet used for exact algorithms and for planar graphs. As concrete consequences of our main result, we obtain
$n^{{\mathcal{O}}(\sqrt{k})}$
time algorithms for the following problems:
d
-Scattered Set
in planar graphs (find
k
vertices at pairwise distance
d
);
d
-Dominating Set
/(
k
,
d
)
-Center
in planar graphs (find
k
vertices such that every vertex is at distance at most
d
from these vertices); select
k
pairwise disjoint connected vertex sets from a given collection; select
k
pairwise disjoint disks in the plane (of possibly different radii) from a given collection; cover a set of points in the plane by selecting
k
disks/axis-parallel squares from a given collection. We complement these positive results with lower bounds suggesting that some similar, but slightly more general problems (such as covering points with axis-parallel rectangles) do not admit
$n^{{\mathcal{O}}(\sqrt{k})}$
time algorithms.