Improved Approximation Algorithms for Patrol-Scheduling with Min-Max Latency Using Multiclass Minimum Spanning Forests

In a weighted complete metric graph \(G=(V, E, w, d)\) , with \(w: V \rightarrow \mathbb {R}^+\) determining the importance of vertices and \(d: E\rightarrow \mathbb {R}^+\) defining the distance between vertices, consider \(k\ge 1\) infinite walks \(\mathcal {W}=\{W_1,\dots , W_k\}\) undertaken by robots \(r_1,\dots ,r_k\) throughout G. The term latency \(L(\mathcal {W},v)\) is used to describe the maximum interval between successive visits to the vertex v by any robot in \(\{r_1,\dots , r_k\}\) . The (maximum) weighted latency of \(\mathcal {W}\) in G is defined as \(L(\mathcal {W},G)=\max _{v\in V}w(v)\cdot L(\mathcal {W},v)\) , indicating the longest period a vertex remains unvisited, with adjustments made based on the weight assigned to a vertex to denote its significance. The goal of the k-Robot Patrol-Scheduling Problem is to minimize the weighted latency, thereby ensuring no graph vertex is neglected for extended periods. Addressed as a challenging issue in [Gąsieniec et al., Journal of Computer and System Sciences, 2024] (where the problem is referred to as the (continuous) Bamboo Garden Trimming Problem), it holds crucial relevance for fields requiring the methodical deployment of robots for tasks such as surveillance, monitoring, and exploration within metric graph-modeled environments. In this paper, we give improved approximation algorithms for \(k\ge 1\) robots that utilize a novel strategy of constructing multi-class minimum spanning forests. For the single robot case, i.e., \(k=1\) , we give a 5h-approximation algorithm which improves the \((8h+14)\) -approximation algorithm given in [Alamdari et al., International Journal of Robotics Research, 2014], where \(h=\lfloor \log _2 \frac{w_{\text {max}}}{w_{\text {min}}}\rfloor + 1\) , \(w_{\text {max}}=\max _{v\in V}w(v)\) , and \(w_{\text {min}}=\min _{v\in V}w(v)\) . For \(k\ge 2\) , we give an approximation algorithm running in \(O(n^2\log L^*)\) time achieving an \(O(k\cdot \log \frac{w_{\text {max}}}{w_{\text {min}}})\) -approximation solution, where n is the number of vertices in the input graph and \(L^*\) is the optimum weighted latency. The adoption of a multi-class minimum spanning forest strategy marks a significant improvement over the previous \(O(k^2\cdot \log \frac{w_{\text {max}}}{w_{\text {min}}})\) -approximation algorithm [Afshani et al., WAFR 2020], not only for the approximation ratio but also for the running time of that algorithm, thus demonstrating considerable progress in this field of research.