Loading...
Fast approximation algorithms for multiple coverage with unit disks
Gao, Xuening Guo, Longkun Liao, Kewen
Gao, Xuening
Guo, Longkun
Liao, Kewen
Author
Abstract
Effective monitoring of applications in wireless sensor networks can be underpinned by the multiple coverage problem with unit disks. In the problem, we are given a set of targets T = {t 1 , t 2 , …, t n } distributed in the plane, where t i needs to be covered f(t i ) times for any positive integer f(t i ). The aim is to place a minimum number of disks, such that all the targets can be covered as desired. In the paper, we first present a 5-approximation algorithm with runtime O(n + m) for m = max i {f(t i )}. Then, we give a theoretically improved 4-approximation algorithm, albeit with an increased time complexity to O(n 2 ). In addition, we consider the online setting where targets arrive in sequence and upon each arrival the corresponding coverage disk must be placed. For this setting, we devise an online algorithm with a competitive ratio of 6 and constant update time. To verify aforementioned theoretical findings, numerical experiments are conducted to demonstrate and compare the practical performance of the proposed algorithms.
Keywords
approximation algorithm, multiple coverage, independent set, unit disk
Date
2022
Type
Conference paper
Journal
Book
2022 IEEE 23rd international symposium on a world of wireless, mobile and multimedia networks : WoWMoM 2022
Volume
Issue
Page Range
185-193
Article Number
ACU Department
Peter Faber Business School
Faculty of Law and Business
Faculty of Law and Business
Collections
Relation URI
Source URL
Open Access Status
License
All rights reserved
File Access
Controlled