Approximation Algorithm for Prize-Collecting Constraint Sweep Edge Cover Problem with Base Stations

We consider the prize-collecting constraint sweep edge cover problem with base stations in metric graphs, with a deployment cost \(c\) for each mobile sensor at any vertex. We need to select a collection of mobile sensors together with their assigned trajectories such that the total cost, which is the sum of the sensor deployment costs and the penalties for edges not covered by any route, is minimized. This problem is NP-hard. We provide an approximation algorithm with time complexity \( O(n^2) \) , which guarantees a solution with an objective value at most \( 4 \cdot OPT + c \) , where \( n \) is the number of vertices and \( OPT \) represents the optimal value.