# 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
Full Text: