TY - GEN

T1 - The Euclidean k-supplier problem

AU - Nagarajan, Viswanath

AU - Schieber, Baruch

AU - Shachnai, Hadas

N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

PY - 2013

Y1 - 2013

N2 - 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., minS⊆F: |S|=kmax v∈C d(v,S), where d(v,S) = minu∈S d(v,u) is the minimum distance of client v to any facility in S. We present a 1 + √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 √7 ≈ 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·log2 n) time algorithm for Euclidean k-supplier in constant dimensions that achieves an approximation ratio of 2.965, where n = |C∪F|.

AB - 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., minS⊆F: |S|=kmax v∈C d(v,S), where d(v,S) = minu∈S d(v,u) is the minimum distance of client v to any facility in S. We present a 1 + √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 √7 ≈ 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·log2 n) time algorithm for Euclidean k-supplier in constant dimensions that achieves an approximation ratio of 2.965, where n = |C∪F|.

UR - http://www.scopus.com/inward/record.url?scp=84875527377&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84875527377&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-36694-9_25

DO - 10.1007/978-3-642-36694-9_25

M3 - Conference contribution

AN - SCOPUS:84875527377

SN - 9783642366932

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 290

EP - 301

BT - Integer Programming and Combinatorial Optimization - 16th International Conference, IPCO 2013, Proceedings

T2 - 16th Conference on Integer Programming and Combinatorial Optimization, IPCO 2013

Y2 - 18 March 2013 through 20 March 2013

ER -