An Exact Algorithm for the Minimum Power Partial Multi-Cover Problem on a Line

Sensor coverage is a fundamental problem in wireless networks. This paper investigates the Minimum Power Partial Multi-Cover problem on a Line (MinPowPMC-L). The objective is to allocate power to sensors such that a specified number of target points have their (multi-)coverage requirements satisfied and the total power is minimized. We identify a flaw in a previous work and correct it by proposing a dynamic programming algorithm that runs in polynomial time under the assumption that the maximum coverage requirement is upper bounded by a constant.