K-coverage optimization is widely used in healthcare environments, which minimizing the number of directional receivers that guarantee a given region is covered k times. As K-coverage optimization is NP-hard, a common...
详细信息
ISBN:
(纸本)9783319633091;9783319633084
K-coverage optimization is widely used in healthcare environments, which minimizing the number of directional receivers that guarantee a given region is covered k times. As K-coverage optimization is NP-hard, a commonly used approach for finding the optimal solution is integer linear programming. However, it can be slow for many practical instances. In this article, we propose an exact dynamic programming algorithm based on tree-decomposition. A probability-distribution density function is introduced to describe the relative importance of various areas and compute the minimal optimized sub-structures. We also show that this algorithm can be easily extended to provide exact solutions for different coverage ratio requirements. When compared with the ILP approach and greedy algorithm, our algorithm provides accurate solutions without scarifying too much on efficiency.
暂无评论