  We consider the following surveillance problem: Given a set $P$ of $n$ sites
in a metric space and a set of $k$ robots with the same maximum speed, compute
a patrol schedule of minimum latency for the robots. Here a patrol schedule
specifies for each robot an infinite sequence of sites to visit (in the given
order) and the latency $L$ of a schedule is the maximum latency of any site,
where the latency of a site $s$ is the supremum of the lengths of the time
intervals between consecutive visits to $s$. When $k=1$ the problem is
equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. We
have two main results. We consider cyclic solutions in which the set of sites
must be partitioned into $\ell$ groups, for some~$\ell \leq k$, and each group
is assigned a subset of the robots that move along the travelling salesman tour
of the group at equal distance from each other. Our first main result is that
approximating the optimal latency of the class of cyclic solutions can be
reduced to approximating the optimal travelling salesman tour on some input,
with only a $1+\varepsilon$ factor loss in the approximation factor and an
$O\left(\left( k/\varepsilon \right)^k\right)$ factor loss in the runtime, for
any $\varepsilon >0$. Our second main result shows that an optimal cyclic
solution is a $2(1-1/k)$-approximation of the overall optimal solution. Note
that for $k=2$ this implies that an optimal cyclic solution is optimal overall.
The results have a number of consequences. For the Euclidean version of the
problem, for instance, combining our results with known results on Euclidean
TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields
a $(2(1-1/k)+\varepsilon)$-approximation of the optimal unrestricted solution.
If the conjecture mentioned above is true, then our algorithm is actually a
PTAS for the general problem in the Euclidean setting.
