English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the problem of finding patrol schedules for $k$ robots to visit agiven set of $n$ sites in a metric space. Each robot has the same maximum speedand the goal is to minimize the weighted maximum latency of any site, where thelatency of a site is defined as the maximum time duration between consecutivevisits of that site. The problem is NP-hard, as it has the traveling salesmanproblem as a special case (when $k=1$ and all sites have the same weight). Wepresent 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 siteshave the same weight, we present a polynomial-time algorithm to solve theproblem exactly. If the sites may have different weights, we present a$12$-approximate solution, which runs in polynomial time when the number ofrobots, $k$, is a constant.

Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency