Patrolling a Path Connecting a Set of Points with Unbalanced Frequencies of Visits

Chuangpishit, Huda, Czyzowicz, Jurek, Gasieniec, Leszek ORCID: 0000-0003-1809-9814, Georgiou, Konstantinos, Jurdzinski, Tomasz and Kranakis, Evangelos (2018) Patrolling a Path Connecting a Set of Points with Unbalanced Frequencies of Visits. In: 44th International Conference on Current Trends in Theory and Practice of Computer Science, 2018-1-29 - 2018-2-2, Krems an der Donau, Austria.

Text 1710.00466v1.pdf - Published version Download (658kB)

Abstract

Patrolling consists of scheduling perpetual movements of a collection of mobile robots, so that each point of the environment is regularly revisited by any robot in the collection. In previous research, it was assumed that all points of the environment needed to be revisited with the same minimal frequency. In this paper we study efficient patrolling protocols for points located on a path, where each point may have a different constraint on frequency of visits. The problem of visiting such divergent points was recently posed by Gasieniec et al. in [13], where the authors study protocols using a single robot patrolling a set of $n$ points located in nodes of a complete graph and in Euclidean spaces. The focus in this paper is on patrolling with two robots. We adopt a scenario in which all points to be patrolled are located on a line. We provide several approximation algorithms concluding with the best currently known $\sqrt 3$-approximation.

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	cs.DC, cs.DC, cs.DS
Depositing User:	Symplectic Admin
Date Deposited:	06 Oct 2017 09:56
Last Modified:	19 Jan 2023 06:53
DOI:	10.1007/978-3-319-73117-9_26
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3009808