コンピュータ科学特別講義VIII (See syllabus for the overall schedule of the course.)

Questions and comments are welcome! → kawamura@graco.c.u-tokyo.ac.jp

In *patrolling* problems, several mobile agents move around in a given region and try to cooperate so that every point in the region is (perpetually) visited sufficiently often (that is, no point should be left unattended for any time period of specified length). Problems of this kind are studied with various motivations and in various forms: the agents may have the same or different speeds; the terrain may be a line, a cycle, or more general graphs; the points to be visited may be the whole or a (finite) part of the terrain. Finding an optimal patrolling strategy is not straightforward, even in the simplest settings. In this seminar, I will introduce some results and open questions about properties of and algorithms for optimal patrolling and related scheduling problems, with some emphasis on how interesting theoretical questions have been conceived, explored, and answered in recent studies including the speaker's.

- A. Dumitrescu and C. D. Tóth, Computational geometry column 59: Patrolling problems in a geometric network,
*ACM SIGACT News*, 45(2), 68–72, 2014. - My small survey (PDF, in Japanese) on optimal patrolling, Scheduling Symposium, Tokyo, September 2015