Minimum power partial multi-cover on a line

This paper studies the minimum power partial multi-cover problem on a line (MinPowPMC-Line), the goal of which is to find an assignment of powers to sensors such that at least a required number of points are covered up to their covering requirements. We first present an LP method to show that the minimum power multi-cover problem on a line (without partial covering requirement) is solvable in polynomial time. But this method no longer works when facing partial covering requirement. We turn to dynamic programming method to find an optimal solution for MinPowPMC-Line in time O ( n 4 m 1 + 2 ( c r m a x ) ), where n, m are the number of points and the number of sensors, respectively, and c r m a x denotes the maximum covering requirement of elements. So, this problem is polynomial-time solvable when c r max is upper bounded by a constant.

Authors

• Wei Liang Beijing Institute of Technology Yangtze Delta Region Academy of Beijing Institute of Technology, Jiaxing, China
• Menghong Li
• Zhao Zhang Hefei University of Technology, Yunnan Key Laboratory of Software Engineering
• Xiaohui Huang

Keywords

• Partial multi-cover
• Linear programming
• Totally unimodular
• Dynamic programming