一种用于移动传感器预算扫频覆盖的常数近似算法

《IEEE Transactions on Networking》：A Constant-Approximation Algorithm for Budgeted Sweep Coverage With Mobile Sensors

本文提出首个针对预算驱动的清扫覆盖问题（BSC）的常近似算法，通过解决多方向导问题（MOP）并构建相应解，为优化移动传感器部署提供新方法，推动组合优化任务发展。

　　

摘要：

在本文中，我们提出了第一个用于预算扫描覆盖问题（BSC）的常数近似算法。BSC涉及为多个移动传感器（也称为机器人）设计路线，以便它们定期从兴趣点（PoIs）收集尽可能多的信息。为了解决这个问题，我们首先研究了多定向问题（MOP）。MOP的目标是在遵守预算限制m的情况下，找到一组m个顶点不相交的路径，以覆盖尽可能多的顶点。我们为MOP开发了一个常数近似算法，并利用它实现了BSC的常数近似。我们的发现为优化移动传感器部署及相关组合优化任务开辟了新的可能性。