Fence patrolling by mobile agents with distinct speeds

Akitoshi Kawamura; Yusuke Kobayashi

doi:10.1007/978-3-642-35261-4_62

Fence patrolling by mobile agents with distinct speeds

Akitoshi Kawamura, Yusuke Kobayashi

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

21 Citations (Scopus)

Abstract

Suppose we want to patrol a fence (line segment) using k mobile agents with 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 ≤ 3.

Original language	English
Title of host publication	Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings
Publisher	Springer Verlag
Pages	598-608
Number of pages	11
ISBN (Print)	9783642352607
DOIs	https://doi.org/10.1007/978-3-642-35261-4_62
Publication status	Published - 2012
Event	23rd International Symposium on Algorithms and Computation, ISAAC 2012 - Taipei, Taiwan, Province of China Duration: Dec 19 2012 → Dec 21 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7676 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	23rd International Symposium on Algorithms and Computation, ISAAC 2012
Country/Territory	Taiwan, Province of China
City	Taipei
Period	12/19/12 → 12/21/12

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-35261-4_62

Cite this

Kawamura, A., & Kobayashi, Y. (2012). Fence patrolling by mobile agents with distinct speeds. In Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings (pp. 598-608). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7676 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-35261-4_62

Fence patrolling by mobile agents with distinct speeds. / Kawamura, Akitoshi; Kobayashi, Yusuke.
Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings. Springer Verlag, 2012. p. 598-608 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7676 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kawamura, A & Kobayashi, Y 2012, Fence patrolling by mobile agents with distinct speeds. in Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7676 LNCS, Springer Verlag, pp. 598-608, 23rd International Symposium on Algorithms and Computation, ISAAC 2012, Taipei, Taiwan, Province of China, 12/19/12. https://doi.org/10.1007/978-3-642-35261-4_62

Kawamura A, Kobayashi Y. Fence patrolling by mobile agents with distinct speeds. In Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings. Springer Verlag. 2012. p. 598-608. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-35261-4_62

@inproceedings{4a158bcb7b5b4869b29cc3b09d5f0d18,

title = "Fence patrolling by mobile agents with distinct speeds",

abstract = "Suppose we want to patrol a fence (line segment) using k mobile agents with speeds v1, . . . , 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 (v1 + ··· + vk)/2, which is achieved by the simple strategy where each agent i moves back and forth in a segment of length vi/2. We disprove this conjecture by a counterexample involving k = 6 agents. We also show that the conjecture is true for k ≤ 3.",

author = "Akitoshi Kawamura and Yusuke Kobayashi",

year = "2012",

doi = "10.1007/978-3-642-35261-4_62",

language = "English",

isbn = "9783642352607",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "598--608",

booktitle = "Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Fence patrolling by mobile agents with distinct speeds

AU - Kawamura, Akitoshi

AU - Kobayashi, Yusuke

PY - 2012

Y1 - 2012

N2 - Suppose we want to patrol a fence (line segment) using k mobile agents with speeds v1, . . . , 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 (v1 + ··· + vk)/2, which is achieved by the simple strategy where each agent i moves back and forth in a segment of length vi/2. We disprove this conjecture by a counterexample involving k = 6 agents. We also show that the conjecture is true for k ≤ 3.

AB - Suppose we want to patrol a fence (line segment) using k mobile agents with speeds v1, . . . , 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 (v1 + ··· + vk)/2, which is achieved by the simple strategy where each agent i moves back and forth in a segment of length vi/2. We disprove this conjecture by a counterexample involving k = 6 agents. We also show that the conjecture is true for k ≤ 3.

UR - http://www.scopus.com/inward/record.url?scp=84871566287&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84871566287&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-35261-4_62

DO - 10.1007/978-3-642-35261-4_62

M3 - Conference contribution

AN - SCOPUS:84871566287

SN - 9783642352607

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 598

EP - 608

BT - Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings

PB - Springer Verlag

T2 - 23rd International Symposium on Algorithms and Computation, ISAAC 2012

Y2 - 19 December 2012 through 21 December 2012

ER -

Fence patrolling by mobile agents with distinct speeds

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this