嘘を含む比較による最小値最大値発見アルゴリズム

スポンサーリンク

概要

論文の詳細を見る
Pohlは1972年に要素数nの全順序集合における最小値と最大値を同時に発見するためには〓(3n)/2〓-2回の比較が十分であり,また,最悪の場合には必要であることを証明した.ただし,全順序集合は一対比較を行うオラクルとして与えられる.最近,この問題はRenyi-Ulamの嘘つきゲームの文脈でも研究されるようになった.そこでは,オラクルが高々k回正しくない返答を与えることができる.Aignerはkが大きいときに(k+O(√<k>))n回の比較が十分であることを証明した.本研究ではそれに対する改善として,ある定数Cに対して高々(k+1+C)n+O(k^3)回の比較を行うアルゴリズムを与える.知られている下界はある定数Dに対して(k+1+c_k)n-Dという形をしていて,c_0=0.5, c_1=(23)/(32)〓0.605であり,k→∞に対してc_k=Ω(2^<-(5k)/4>)である.
2010-01-18

著者

関連論文

もっと見る

スポンサーリンク