  A classical multi-agent fence patrolling problem asks: What is the maximum
length $L$ of a line that $k$ agents with maximum speeds $v_1,\ldots,v_k$ can
patrol if each point on the line needs to be visited at least once every unit
of time. It is easy to see that $L = \alpha \sum_{i=1}^k v_i$ for some
efficiency $\alpha \in [\frac{1}{2},1)$. After a series of works giving better
and better efficiencies, it was conjectured that the best possible efficiency
approaches $\frac{2}{3}$. No upper bounds on the efficiency below $1$ were
known. We prove the first such upper bounds and tightly bound the optimal
efficiency in terms of the minimum ratio of speeds $s = {v_{\max}}/{v_{\min}}$
and the number of agents $k$. Guided by our upper bounds, we construct a scheme
whose efficiency approaches $1$, disproving the conjecture of Kawamura and
Soejima. Our scheme asymptotically matches our upper bounds in terms of the
maximal speed difference and the number of agents used, proving them to be
asymptotically tight.
  A variation of the fence patrolling problem considers a circular fence
instead and asks for its circumference to be maximized. We consider the
unidirectional case of this variation, where all agents are only allowed to
move in one direction, say clockwise. At first, a strategy yielding $L =
\max_{r \in [k]} r \cdot v_r$ where $v_1 \geq v_2 \geq \dots \geq v_k$ was
conjectured to be optimal by Czyzowicz et al. This was proven not to be the
case by giving constructions for only specific numbers of agents with marginal
improvements of $L$. We give a general construction that yields $L =
\frac{1}{33 \log_e\log_2(k)} \sum_{i=1}^k v_i$ for any set of agents, which in
particular for the case $1, 1/2, \dots, 1/k$ diverges as $k \rightarrow
\infty$, thus resolving a conjecture by Kawamura and Soejima affirmatively.
