论文标题
多机巡逻队的近似算法与最小最大延迟
Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
论文作者
论文摘要
我们考虑找到$ K $机器人的巡逻计划的问题，以访问指标空间中的一组$ n $站点。每个机器人都具有相同的最大速度，目标是最大程度地减少任何站点的加权最大延迟，其中将站点的延迟定义为该站点连续访问之间的最大持续时间。问题是NP-HARD，因为它具有旅行推销员问题作为特殊情况（当$ k = 1 $且所有网站都具有相同的权重时）。我们提出了一个多项式时间算法，其近似值为$ O（k^2 \ log \ frac {w _ {\ max}} {w _ {\ min}}）$，其中$ w _ {\ max} $ and $ w _ {\ max} $ and $ w _ {\ min} $的最大程度和最大的重量。此外，我们考虑了站点以1D为单位的特殊情况。当所有站点都具有相同的权重时，我们会提出一种多项式时间算法来精确解决问题。如果这些站点的权重不同，我们会提供一个$ 12 $ - 备用的解决方案，该解决方案在多项式时间内运行时，机器人的数量$ k $是一个常数。
We consider the problem of finding patrol schedules for $k$ robots to visit a given set of $n$ sites in a metric space. Each robot has the same maximum speed and the goal is to minimize the weighted maximum latency of any site, where the latency of a site is defined as the maximum time duration between consecutive visits of that site. The problem is NP-hard, as it has the traveling salesman problem as a special case (when $k=1$ and all sites have the same weight). We present a polynomial-time algorithm with an approximation factor of $O(k^2 \log \frac{w_{\max}}{w_{\min}})$ to the optimal solution, where $w_{\max}$ and $w_{\min}$ are the maximum and minimum weight of the sites respectively. Further, we consider the special case where the sites are in 1D. When all sites have the same weight, we present a polynomial-time algorithm to solve the problem exactly. If the sites may have different weights, we present a $12$-approximate solution, which runs in polynomial time when the number of robots, $k$, is a constant.
