Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
The Euclidean k-Supplier Problem in
verfasst von : Manjanna Basappa, Ramesh K. Jallu, Gautam K. Das, Subhas C. Nandy
Erschienen in: Algorithms for Sensor Systems
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
Abstract
In this paper, we consider k-supplier problem in
. Here, two sets of points \(\mathcal{P}\) and \(\mathcal{Q}\) are given. The objective is to choose a subset \(Q_{opt} \subseteq \mathcal{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 \(\mathcal{P}\).
. Here, two sets of points \(\mathcal{P}\) and \(\mathcal{Q}\) are given. The objective is to choose a subset \(Q_{opt} \subseteq \mathcal{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 \(\mathcal{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+\sqrt{3})\)-approximation algorithm, but the results produced by our algorithm significantly outperforms that of Nagarajan et al.’s algorithm.