Advertisement
Published in:
2019 | OriginalPaper | Chapter
Capacitated Discrete Unit Disk Cover
Authors : Pawan K. Mishra, Sangram K. Jena, Gautam K. Das, S. V. Rao
Published in: WALCOM: Algorithms and Computation
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Consider a capacitated version of the discrete unit disk cover problem as follows: consider a set \(P= \{p_1,p_2, \cdots ,p_n\}\) of n customers and a set \(Q=\{q_1,q_2, \cdots ,q_m\}\) of m service centers. A service center can provide service to at most \(\alpha ( \in \mathbb {N})\) number of customers. Each \(q_i \in Q\) \((i=1,2, \cdots ,m)\) has a preassigned set of customers to which it can provide service. The objective of the capacitated covering problem is to provide service to each customer in P by at least one service center in Q. In this paper, we consider the geometric version of the capacitated covering problem, where the set of customers and set of service centers are two point sets in the Euclidean plane. A service center can provide service to a customer if their Euclidean distance is less than or equal to 1. We call this problem as \((\alpha , P, Q)\)-covering problem. For the \((\alpha , P, Q)\)-covering problem, we propose an \(O(\alpha mn(m+n))\) time algorithm to check feasible solution for a given instance. We also prove that the \((\alpha , P, Q)\)-covering problem is NP-complete for \(\alpha \ge 3\) and it admits a PTAS.