Efficient approximation algorithms for offline and online unit disk multiple coverage

• Published in: Computers & electrical engineering 2022-12, Vol.104, p.108444, Article 108444
• Main Authors: Gao, Xuening, Guo, Longkun, Liao, Kewen
• Format: Article
• Language: English
• Subjects: Approximation algorithm; Disk coverage; Linear runtime; Multiple coverage; Online algorithm
• ISSN: 0045-7906; 1879-0755
• DOI: 10.1016/j.compeleceng.2022.108444

Multiple coverage with unit disks is a problem widely seen in monitoring applications of wireless sensor networks. In this problem, let T=t1,t2,…,tn be a set of targets to be covered (or monitored) which are distributed on the plane. Each target ti∈T is required to be covered by f(ti) disks for the purpose of energy efficiency or fault tolerance. The objective is to decide where on the plane to place the disks such that all the targets can be covered with a minimum number of disks. The problem does not admit any polynomial time exact solution as its special case of single coverage with unit disks is already NP-hard. In the paper, we present both offline and online approximation results for the problem where in the online setting disks must be placed upon each arrival of targets. We first give an offline 5-approximation algorithm with linear time and space complexity via exploiting efficient data structures. The algorithm can be easily adapted as an online 5-competitive algorithm. Then, we propose an improved offline algorithm attaining 4-approximation. Finally, we devise an efficient online algorithm with a constant average update time and a competitive ratio of 6. Numerical experiments are also carried out to empirically test and compare our proposed approximation algorithms. [Display omitted] •Propose a 5-approximation algorithm for offline UDMC with linear time and space complexity.•Improve the approximation ratio to 4 with quadratic running time for offline UDMC.•Design a 6-competitive algorithm for online UDMC with a constant average update time.