Abstract
We consider the following surveillance problem: Given a set P of n sites in a metric space and a
set R 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. For k ⩾ 2 (which is the version we are interested in) the problem becomes even more
challenging; for example, it is not even clear if the decision version of the problem is decidable, in
particular in the Euclidean case.
We have two main results. We consider cyclic solutions in which the set of sites must be
partitioned into ℓ groups, for some ℓ ⩽ 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 + ε factor
loss in the approximation factor and an O
(k/ε)
k
factor loss in the runtime, for any ε > 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.
We conjecture that this is true for k ⩾ 3 as well.
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) + ε)-approximation of the optimal unrestricted
(not necessarily cyclic) solution. If the conjecture mentioned above is true, then our algorithm is
actually a PTAS for the general problem in the Euclidean setting. Similar results can be obtained
by combining our results with other known TSP algorithms in non-Euclidean metrics
set R 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. For k ⩾ 2 (which is the version we are interested in) the problem becomes even more
challenging; for example, it is not even clear if the decision version of the problem is decidable, in
particular in the Euclidean case.
We have two main results. We consider cyclic solutions in which the set of sites must be
partitioned into ℓ groups, for some ℓ ⩽ 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 + ε factor
loss in the approximation factor and an O
(k/ε)
k
factor loss in the runtime, for any ε > 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.
We conjecture that this is true for k ⩾ 3 as well.
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) + ε)-approximation of the optimal unrestricted
(not necessarily cyclic) solution. If the conjecture mentioned above is true, then our algorithm is
actually a PTAS for the general problem in the Euclidean setting. Similar results can be obtained
by combining our results with other known TSP algorithms in non-Euclidean metrics
| Original language | English |
|---|---|
| Title of host publication | Symposium on Computational Geometry |
| Publisher | Dagstuhl Publishing |
| Number of pages | 14 |
| DOIs | |
| Publication status | Published - 2022 |
Keywords
- CG
- DS
- GRAPH