arXiv preprint ·
Constant-Factor Approximation Algorithms for Weighted Budgeted Multisensor Sweep Coverage
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Sweep coverage requires each point of interest (PoI) to be revisited by some mobile sensor at least once during every sweep period, and it underlies persistent patrolling, environmental monitoring, and infrastructure inspection. Given a set of $N$ PoIs, each associated with a nonnegative weight representing its importance, the weighted budgeted sweep coverage problem (WB-SCP) seeks routing trajectories for a budget of $M\leq N$ identical mobile sensors with a common maximum speed to maximize the total weight of the sweep-covered PoIs. For the unweighted special case in which every PoI has unit weight, the first constant-factor approximation algorithm achieves a ratio of $0.0116-O(\varepsilon)$ for any constant $\varepsilon>0$, and whether the WB-SCP itself admits such an algorithm has remained open. In this paper, we resolve this open question by proposing two constant-factor approximation algorithms for the WB-SCP. The first converts any bifactor $(α,β)$-approximation algorithm into a $β/(2α)$-approximation algorithm, yielding a ratio of $1/16=0.0625$. The second builds on a greedy maximum-coverage framework and improves the ratio to $1-e^{-1/2}-\varepsilon$ for any fixed $\varepsilon>0$. Both algorithms also improve the best-known ratio for the unweighted case, and the second extends to heterogeneous sensors with different speeds while preserving the same guarantee.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Quadratic-Time Barriers from Self-Referential SAT
Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
GreedTok is a Constant-Factor Approximation for Partition-Cover Tokenization
Constant-Factor Approximations for the Biased Traveling Salesman Problem and Its Path Variant
A Simple Discrete Newton Method for the Quickest Transshipment Problem
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.