A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917755294318592 |
|---|---|
| author | Liang, Wei Tang, Shaojie Zhang, Zhao |
| author_facet | Liang, Wei Tang, Shaojie Zhang, Zhao |
| contents | In this paper, we present the first constant-approximation algorithm for {\em budgeted sweep coverage problem} (BSC). The BSC involves designing routes for a number of mobile sensors (a.k.a. robots) to periodically collect information as much as possible from points of interest (PoIs). To approach this problem, we propose to first examine the {\em multi-orienteering problem} (MOP). The MOP aims to find a set of $m$ vertex-disjoint paths that cover as many vertices as possible while adhering to a budget constraint $B$. We develop a constant-approximation algorithm for MOP and utilize it to achieve a constant-approximation for BSC. Our findings open new possibilities for optimizing mobile sensor deployments and related combinatorial optimization tasks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_12468 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors Liang, Wei Tang, Shaojie Zhang, Zhao Discrete Mathematics Data Structures and Algorithms In this paper, we present the first constant-approximation algorithm for {\em budgeted sweep coverage problem} (BSC). The BSC involves designing routes for a number of mobile sensors (a.k.a. robots) to periodically collect information as much as possible from points of interest (PoIs). To approach this problem, we propose to first examine the {\em multi-orienteering problem} (MOP). The MOP aims to find a set of $m$ vertex-disjoint paths that cover as many vertices as possible while adhering to a budget constraint $B$. We develop a constant-approximation algorithm for MOP and utilize it to achieve a constant-approximation for BSC. Our findings open new possibilities for optimizing mobile sensor deployments and related combinatorial optimization tasks. |
| title | A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors |
| topic | Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.12468 |