文献

J-GLOBAL ID：201002218868964446   整理番号：10A0193077

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

Minimum and maximum against k lies

著者 (5件)： HOFFMANN Michael (スイス連邦工科大 チューリヒ校) ,  MATOUSEK Jiri (スイス連邦工科大 チューリヒ校) ,  MATOUSEK Jiri (カレル大 応用数) ,  岡本吉央 (東京工大 大学院情報理工学研究科) ,  ZUMSTEIN Philipp (スイス連邦工科大 チューリヒ校)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 109  号： 391(COMP2009 39-48)  ページ： 51-56  発行年： 2010年01月18日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： Pohlは1972年に要素数nの全順序集合における最小値と最大値を同時に発見するためには[3n/2]-2回の比較が十分であり,また,最悪の場合には必要であることを証明した。ただし,全順序集合は一対比較を行うオラクルとして与えられる。最近,この問題はRenyi-Ulamの嘘つきゲームの文脈でも研究されるようになった。そこでは,オラクルが高々k回正しくない返答を与えることができる。Aignerはkが大きいときに(k+O(√<span style=text-decoration:overline>X</span>(X=k)))n回の比較が十分であることを証明した。本研究ではそれに対する改善として,ある定数Cに対して高々(k+1+C)n+O(k³)回の比較を行うアルゴリズムを与える。知られている下界はある定数Dに対して(k+1+c_k)n-Dという形をしていて,c₀=0.5,c₁=23/32≒0.605であり,k→∞に対してc_k=Ω(2^-5k/4)である。(著者抄録)

シソーラス用語： *最小値 ,  *最大値 ,  一対比較法 ,  *計算機アルゴリズム ,  数値計算 ,  誤り ,  *集合 ,  情報理論 ,  ゲーム理論 ,  下限 ,  有向グラフ
準シソーラス用語： Renyiエントロピー

分類 (1件)： 計算理論  (JB02000A)

引用文献 (9件)：

• AIGNER, M. Finding the maximum and the minimum. Discrete Applied Mathematics. 1997, 74, 1-12
• DEPPE, C. Coding with feedback and searching with lies. Entropy, Search, Complexity, Bolyai Society Mathematical Studies. 2007, 16, 27-70
• DOR, D. Selecting the median. SIAM Journal on Computing. 1999, 28, 1722-1758
• FORD, L. R. Jr. Maximal flow through a network. Canadian Journal of Mathematics. 1956, 8, 399-404
• GERBNER, D. Finding the maximum and minimum elements with one lie

タイトルに関連する用語 (4件)： 最小値 ,  最大値 ,  発見 ,  アルゴリズム