4810-1212 Seminar on Computer Science VIII (Winter 2016)

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

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

December 14: Open problems in patrolling and periodic scheduling

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.