2024/08/22 by Liang Wei, Shaojie Tang, Liang, Wei +3
Computer Science · #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2408.12468
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.