  Suppose that a set of mobile agents, each with a predefined maximum speed,
want to patrol a fence together so as to minimize the longest time interval
during which a point on the fence is left unvisited. In 2011, Czyzowicz,
G\k{a}sieniec, Kosowski and Kranakis studied this problem for the settings
where the fence is an interval (a line segment) and a circle, and conjectured
that the following simple strategies are always optimal: for Interval
Patrolling, the simple strategy partitions the fence into subintervals, one for
each agent, and lets each agent move back and forth in the assigned subinterval
with its maximum speed; for Circle Patrolling, the simple strategy is to choose
a number r, place the r fastest agents equidistantly around the circle, and
move them at the speed of the rth agent. Surprisingly, these conjectures were
then proved false: schedules were found (for some settings of maximum speeds)
that slightly outperform the simple strategies. In this paper, we are
interested in the ratio between the performances of optimal schedules and
simple strategies. For the two problems, we construct schedules that are 4/3
times (for Interval Patrolling) and 21/20 times (for Circle Patrolling) as
good, respectively, as the simple strategies. We also propose a new variant, in
which we want to patrol a single point under the constraint that each agent can
only visit the point some predefined time after its previous visit. We obtain
some similar ratio bounds and NP-hardness results related to this problem.
