質問など遠慮なくどうぞ→kawamura@kurims.kyoto-u.ac.jp
幾つかある仕事のそれぞれについて、連続する○○日には必ず一度以上やるべしという日数が指定されています。これを満し続けながら毎日いずれか一つだけ仕事をできるでしょうか。勿論これが可能であるには指定された日数の逆数の和が1以下である必要がありますが、逆にこの逆数和が或る程度小さければ十分であることも判っています。輪番割当(pinwheel scheduling)とよばれるこの問題について、必要条件や十分条件、判定する方法(アルゴリズム)やその効率、「一度以上」を「一度以下」や「ちょうど一度」にした変種などを紹介します。
なお本講義は、講師自身が今年書いている論文とそれに関連する研究動向の解説です。発見や試行錯誤の経緯、うまくいった所、ガッカリな所、もう少しで解けそうな未解決問題など、研究の進め方に関する裏話もしたいと思います。