TY - JOUR
T1 - Fence patrolling by mobile agents with distinct speeds
AU - Kawamura, Akitoshi
AU - Kobayashi, Yusuke
N1 - Funding Information:
A preliminary version of this paper was presented at the 23rd International Symposium on Algorithms and Computation []. Supported in part by KAKENHI (Grant-in-Aid for Scientific Research, Japan).
Publisher Copyright:
© 2014, Springer-Verlag Berlin Heidelberg.
PY - 2015/1/1
Y1 - 2015/1/1
N2 - Suppose we want to patrol a fence (line segment) using $$k$$k mobile agents with given speeds $$v _1$$v1,.., $$v _k$$vk 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 _1 + \cdots + v _k)/2$$(v1+⋯+vk)/2, which is achieved by the simple strategy where each agent $$i$$i moves back and forth in a segment of length $$v _i / 2$$vi/2. We disprove this conjecture by a counterexample involving $$k = 6$$k=6 agents. We also show that the conjecture is true for $$k \le 3$$k≤3.
AB - Suppose we want to patrol a fence (line segment) using $$k$$k mobile agents with given speeds $$v _1$$v1,.., $$v _k$$vk 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 _1 + \cdots + v _k)/2$$(v1+⋯+vk)/2, which is achieved by the simple strategy where each agent $$i$$i moves back and forth in a segment of length $$v _i / 2$$vi/2. We disprove this conjecture by a counterexample involving $$k = 6$$k=6 agents. We also show that the conjecture is true for $$k \le 3$$k≤3.
UR - http://www.scopus.com/inward/record.url?scp=85027957380&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85027957380&partnerID=8YFLogxK
U2 - 10.1007/s00446-014-0226-3
DO - 10.1007/s00446-014-0226-3
M3 - Article
AN - SCOPUS:85027957380
SN - 0178-2770
VL - 28
SP - 147
EP - 154
JO - Distributed Computing
JF - Distributed Computing
IS - 2
ER -