Efficient algorithms for max-weighted point sweep coverage on lines

Dieyan Liang, Hong Shen

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


As an important application of wireless sensor networks (WSNs), deployment of mobile sensors to periodically monitor (sweep cover) a set of points of interest (PoIs) arises in various applications, such as environmental monitoring and data collection. For a set of PoIs in an Eulerian graph, the point sweep coverage problem of deploying the fewest sensors to periodically cover a set of PoIs is known to be Non-deterministic Polynomial Hard (NP-hard), even if all sensors have the same velocity. In this paper, we consider the problem of finding the set of PoIs on a line periodically covered by a given set of mobile sensors that has the maximum sum of weight. The problem is first proven NP-hard when sensors are with different velocities in this paper. Optimal and approximate solutions are also presented for sensors with the same and different velocities, respectively. For M sensors and N PoIs, the optimal algorithm for the case when sensors are with the same velocity runs in O(MN) time; our polynomial-time approximation algorithm for the case when sensors have a constant number of velocities achieves approximation ratio12; for the general case of arbitrary 1 velocities, and12 (1 − 1/e) approximation algorithms are presented, respectively, where integer α ≥ 2 is the tradeoff factor between time complexity and approximation ratio.

Original languageEnglish
Article number1457
Pages (from-to)1-19
Number of pages19
Issue number4
Publication statusPublished - 2 Feb 2021
Externally publishedYes


  • Approximation algorithm
  • Integer programming
  • Mobile sensors
  • Sweep coverage
  • WSN


Dive into the research topics of 'Efficient algorithms for max-weighted point sweep coverage on lines'. Together they form a unique fingerprint.

Cite this