Scheduling recurring tasks

Date
2024/04/24 Wed 16:45 - 17:45
Room
RIMS110号室
Speaker
Akitoshi Kawamura
Affiliation
Kyoto University
Abstract

いくつかある仕事のそれぞれについて、どの連続する○○日にも一度以上やるべしと
いう日数が指定されている。これを満しながら毎日ひとつづつ仕事をし続けることがで
きるだろうか。できるためには明らかに、指定された日数の逆数の和が 1 以下である必
要があるが、逆にこの逆数和が或る程度小さければ十分であることも判っている。本講
演ではこの問題について、必要条件や十分条件、判定する方法(アルゴリズム)やその効
率、「一度以上」を「一度以下」や「ちょうど一度」にした変種や、これらに関する最近
の研究動向などを解説する。