Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
  • Metaadatok
Tartalom: http://real.mtak.hu/31195/
Archívum: MTA Könyvtár
Gyűjtemény: Status = Published


Type = Article
Cím:
Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
Létrehozó:
Marx, Dániel
Pilipczuk, M.
Dátum:
2015
Téma:
QA74 Analysis / analízis
QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Tartalmi leírás:
We study a general family of facility location problems de-
?ned on planar graphs and on the 2-dimensional plane. In these problems,
a subset of
k
objects has to be selected, satisfying certain packing (dis-
jointness) and covering constraints. Our main result is showing that, for
each of these problems, the
n
O
(
k
)
time brute force algorithm of selecting
k
objects can be improved to
n
O
(
p
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
O
(
p
k
)
time algorithms for the
following problems:
d
-Scattered Set
in planar graphs (?nd
k
vertices
at pairwise distance
d
);
d
-Dominating Set
/(
k; d
)
-Center
in planar
graphs (?nd
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
di?erent 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
O
(
p
k
)
time algorithms.
Típus:
Article
NonPeerReviewed
Formátum:
text
Azonosító:
Marx, Dániel and Pilipczuk, M. (2015) Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9294. pp. 865-877.
Kapcsolat: