Fast approximation algorithms for multiple coverage with unit disks
Conference paper
Gao, Xuening, Guo, Longkun and Liao, Kewen. (2022). Fast approximation algorithms for multiple coverage with unit disks. 2022 IEEE 23rd International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM). Belfast, United Kingdom 14 - 17 Jun 2022 IEEE Computer Society. pp. 185-193 https://doi.org/10.1109/WoWMoM54355.2022.00037
Authors | Gao, Xuening, Guo, Longkun and Liao, Kewen |
---|---|
Type | Conference paper |
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 |
Year | 2022 |
Publisher | IEEE Computer Society |
Digital Object Identifier (DOI) | https://doi.org/10.1109/WoWMoM54355.2022.00037 |
Scopus EID | 2-s2.0-85137121539 |
Publisher's version | License All rights reserved File Access Level Controlled |
Book title | 2022 IEEE 23rd international symposium on a world of wireless, mobile and multimedia networks : WoWMoM 2022 |
Page range | 185-193 |
ISBN | 9781665408769 |
9781665408776 | |
Web address (URL) of conference proceedings | https://ieeexplore.ieee.org/xpl/conhome/9842746/proceeding |
Output status | Published |
Publication dates | |
2022 | |
Online | 09 Aug 2022 |
Publication process dates | |
Deposited | 16 Oct 2023 |
https://acuresearchbank.acu.edu.au/item/8zvy1/fast-approximation-algorithms-for-multiple-coverage-with-unit-disks
Restricted files
Publisher's version
53
total views0
total downloads1
views this month0
downloads this month