×

zbMATH — the first resource for mathematics

The Euclidean \(k\)-supplier problem. (English) Zbl 1377.90053
Goemans, Michel (ed.) et al., Integer programming and combinatorial optimization. 16th international conference, IPCO 2013, Valpara√≠so, Chile, March 18–20, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-36693-2/pbk). Lecture Notes in Computer Science 7801, 290-301 (2013).
Summary: In the \(k\)-supplier problem, we are given a set of clients \(C\) and set of facilities \(F\) located in a metric (\(C \cup 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 \subseteq F: |S| = k } \max_{v \in C } d(v,S)\), where \(d(v,S) = \min_{u \in 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 [D. S. Hochbaum and D. B. Shmoys, “A unified approach to approximation algorithms for bottleneck problems”, J. ACM 33, No. 3, 533–550 (1986; doi:10.1145/5925.5933)] 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 [T. Feder and D. H. Greene, “Optimal algorithms for approximate clustering”, in: Proceedings of the 20th annual ACM symposium on theory of computing, STOC 1988. New York, NY: Association for Computing Machinery (ACM). 434–444 (1988; doi:10.1145/62212.62255)]. Our algorithm is based on a relation to the edge cover problem. We also present a nearly linear \(O(n \cdot \log^{2} n)\) time algorithm for Euclidean \(k\)-supplier in constant dimensions that achieves an approximation ratio of 2.965, where \(n = |C \cup F|\).
For the entire collection see [Zbl 1258.90003].

MSC:
90B80 Discrete location and assignment
68W25 Approximation algorithms
90C27 Combinatorial optimization
PDF BibTeX Cite
Full Text: DOI