本文へスキップします。

【全】メガメニュー
H1

国内研究者論文詳細

日本人論文紹介:詳細

2026/08/12

輪番割当問題の密度閾値予想の証明

論文タイトル
Proof of the density threshold conjecture for pinwheel scheduling.
論文タイトル(訳)
輪番割当問題の密度閾値予想の証明
DOI
10.1073/pnas.2530214123
ジャーナル名
Proceedings of the National Academy of Sciences of the United States of America
巻号
Proc. Natl. Acad. Sci. U.S.A. 123 (32) e2530214123
著者名(敬称略)
河村 彰星
所属
京都大学数理解析研究所
著者からのひと言
素朴な設定でありながら解析の難しい問題でしたが、大規模計算の手法がうまく効いて予想の解決に至ったのは幸運でした。人間が読める「きれいな」証明が今後得られる望みも捨ててはいませんが、ともあれ近年のAIをはじめとする計算機技術の著しい進歩は、数学研究に新たな可能性と展開をもたらしつつあります。コンピュータの高度な探索・検証能力の活用は、今後も従来の枠組みを超えて我々の数学的理解を大きく進展させるものと期待しています。

抄訳

輪番割当問題では、いくつかある仕事のそれぞれについて、連続する○○日には必ず一度以上やるべしという日数が指定されており、これを満し続けながら毎日いずれか一つだけ仕事をしたい。勿論これが可能であるには指定された日数の逆数の和が 1 以下である必要がある。一方この逆数和が 5/6 以下なら十分である、という陳と銭(1993)の予想が示されたので報告する。証明は有限個の場合を計算機で確かめることでなされた。この有限個で十分であることは、日数を整数から実数へ適切に拡張する議論により示される。この考え方を使うと、仕事が二種類以内であれば逆数和 1 以下が十分であることも簡単に証明できる。また竹叢伐採問題の高速な 4/3 近似算法も得られる。

論文掲載ページへ