抄録
Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3300000, indirect: 990000)
本研究では研究代表者の提案している「劣線形時間パラダイム」を広く展開するための理論研究を行っている。２０２１年度の主な成果は以下の通りである。 (I) 漸進型アルゴリズム(progressive algorithm)の結果をまとめた論文が論文誌に採録・出版された。「漸進型アルゴリズム」とは、データを徐々に読み込みながら段々と精度の高い解を求めていく手法であり、研究代表者によって提案されたものである。我々はこれまでに、「定数時間アルゴリズム」と「全てのデータを読み込む線形以上の計算時間のアルゴリズム」の両者が存在する任意の問題に対し、オーダの意味での各々の計算時間を悪化させることなく、両者を円滑に繋げる漸進型アルゴリズムが構築できることを証明した。これは片側誤り、両側誤りどちらにも適用可能であり、また本技法はグラフに限らず、どのような対象、モデルに対しても適用可能であると考えられ、非常に一般性のある結果である。(II) 機器をスリープ状態にしておくことで再起動の際の時間やエネルギー消費量の節減を図る制御は広く行われている。しかしスリープ状態は少しだが電力を消費し続けるので、長く保つと逆に損になる。この問題はオンライン問題の一種の「スキーレンタル問題」という形で定式化され、その競合比（小さいほど良く、１が最適）は２でこれ以上改善出来ないことが既存研究によって証明され、それが常識とされてきた。しかしその競合比２を与えるアルゴリズムは、最悪に備える為に多くの場合で明らかに無駄と考えられる動作をせざるを得なかった。そこで担当者は、競合比を2+ε（∀ε>0）と僅かに緩和することで、多くの実用的な場合にほぼ無駄が無い様に制御する方法を考案した。その結果を論文誌に投稿し採録・出版された。