betaFeedback

WorksComputer Science

Constant-Factor Approximation Algorithms for Weighted Budgeted Multisensor Sweep Coverage

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 NN 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≤NM\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(ε)0.0116-O(\varepsilon) for any constant ε>0\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α)β/(2α)-approximation algorithm, yielding a ratio of 1/16=0.06251/16=0.0625. The second builds on a greedy maximum-coverage framework and improves the ratio to 1−e−1/2−ε1-e^{-1/2}-\varepsilon for any fixed ε>0\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.

Paper details

vlnc:W_qtdefk6h
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Pro

View statement
Looking for related papers…