Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
The Euclidean k-Supplier Problem
verfasst von : Viswanath Nagarajan, Baruch Schieber, Hadas Shachnai
Erschienen in: Integer Programming and Combinatorial Optimization
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
In the
k-supplier
problem, we are given a set of clients
C
and set of facilities
F
located in a metric (
C
∪
F
,
d
), along with a bound
k
. The goal is to open a subset of
k
facilities so as to minimize the maximum distance of a client to an open facility, i.e., min
S
⊆
F
: |
S
| =
k
max
v
∈
C
d
(
v
,
S
), where
d
(
v
,
S
) = min
u
∈
S
d
(
v
,
u
) is the minimum distance of client
v
to any facility in
S
. We present a
$1+\sqrt{3}<2.74$
approximation algorithm for the
k
-supplier problem in Euclidean metrics. This improves the previously known 3-approximation algorithm [9] which also holds for general metrics (where it is known to be tight). It is NP-hard to approximate Euclidean
k
-supplier to better than a factor of
$\sqrt{7}\approx 2.65$
, even in dimension two [5]. Our algorithm is based on a relation to the
edge cover
problem. We also present a nearly linear
O
(
n
·log
2
n
) time algorithm for Euclidean
k
-supplier in constant dimensions that achieves an approximation ratio of 2.965, where
n
= |
C
∪
F
|.