An Improved PTAS for Covering Targets with Mobile Sensors

2023/05/06 by Nonthaphat Wongwattanakij, Nattawut Phetmak, Wongwattanakij, Nonthaphat +5
Computer Science · Business, Management and Accounting · #Optimization and Search Problems #Facility Location and Emergency Management #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.2305.03946

Abstract

This paper considers a movement minimization problem for mobile sensors. Given a set of n point targets, the k-Sink Minimum Movement Target Coverage Problem is to schedule mobile sensors, initially located at k base stations, to cover all targets minimizing the total moving distance of the sensors. We present a polynomial-time approximation scheme for finding a (1+ε) approximate solution running in time n^O(1/ε) for this problem when k, the number of base stations, is constant. Our algorithm improves the running time exponentially from the previous work that runs in time n^O(1/ε2), without any target distribution assumption. To devise a faster algorithm, we prove a stronger bound on the number of sensors in any unit area in the optimal solution and employ a more refined dynamic programming algorithm whose complexity depends only on the width of the problem.

Related

• Approximation Algorithms for Minimum Sum of Moving-Distance and Opening-Costs Target Coverage Problem
• Point Sweep Coverage on Path
• A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors
• Approximation Algorithms for Minimizing Maximum Sensor Movement for Line Barrier Coverage in the Plane
• Weak Coverage of a Rectangular Barrier