Fence patrolling by mobile agents with distinct speeds

2014/07/30 by Akitoshi Kawamura, Yusuke Kobayashi · 1 citation
Computer Science · #cs.CG #cs.MA #cs.RO

paper · pdf · doi:10.1007/s00446-014-0226-3

12 pages, 8 figures; preliminary version presented at ISAAC 2012

arxiv created 2014/07/30 · arxiv updated 2014/08/21

Abstract

Suppose we want to patrol a fence (line segment) using k mobile agents with given speeds v₁, ..., v_k so that every point on the fence is visited by an agent at least once in every unit time period. Czyzowicz et al. conjectured that the maximum length of the fence that can be patrolled is (v₁ + ... + v_k)/2, which is achieved by the simple strategy where each agent i moves back and forth in a segment of length v_i/2. We disprove this conjecture by a counterexample involving k = 6 agents. We also show that the conjecture is true for k = 2, 3.

Cited by

• Proof of the Density Threshold Conjecture for Pinwheel Scheduling