Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Fence Patrolling by Mobile Agents with Distinct Speeds
verfasst von : Akitoshi Kawamura, Yusuke Kobayashi
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Suppose we want to patrol a fence (line segment) using
k
mobile agents with speeds
v
1
, …,
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
1
+ … +
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
≤ 3.