The Euclidean k-Supplier Problem in R~2

摘要

In this paper, we consider k-supplier problem in R~2. Here, two sets of points P and Q are given. The objective is to choose a subset Q_(opt) ⊆ Q of size at most k such that congruent disks of minimum radius centered at the points in Q_(opt) cover all the points of P. We propose a fixed-parameter tractable (FPT) algorithm for the k-supplier problem that produces a 2-factor approximation result. For |P| = n and |Q| = m, the worst case running time of the algorithm is O(6~k(n + m)log(mn)), which is an exponential function of the parameter k. We also propose a heuristic algorithm based on Voronoi diagram for the k-supplier problem, and experimentally compare the result produced by this algorithm with the best known approximation algorithm available in the literature [Nagarajan, V., Schieber, B., Shachnai, H.: The Euclidean k-supplier problem, In Proc. of 16th Int. Conf. on Integ. Prog. and Comb. Optim., 290-301 (2013)]. The experimental results show that our heuristic algorithm is slower than Nagarajan et al.'s (1 + √3)-approximation algorithm, but the results produced by our algorithm significantly outperforms that of Nagarajan et al.'s algorithm.