嘘を含む比較による最小値最大値発見アルゴリズム  [in Japanese] Minimum and maximum against k lies  [in Japanese]

Search this Article

Author(s)

Abstract

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>)である.

A neat 1972 result of Pohl asserts that 〓(3n)/2〓-2 comparisons are sufficient, and also necessary in the worst case, for finding both the minimum and the maximum of an n-element totally ordered set. The set is accessed via an oracle for pairwise comparisons. More recently, the problem has been studied in the context of the Renyi-Ulam liar games, where the oracle may give up to k false answers. For large k, an upper bound due to Aigner shows that(k+O(√<k>))n comparisons suffice. We improve on this by providing an algorithm with at most (k+1+C)n+O(k^3) comparisons for some constant C. The known lower bounds are of the form (k+1+c_k)n-D, for some constant D, Where c_0=0.5, c_1=(23)/(32)〓0.605, and c_k=Ω(2^<-(5k)/4>) as k→∞. The article is a technical report without peer review, and its polished version will be published elsewhere.

Journal

  • IEICE technical report

    IEICE technical report 109(391), 51-56, 2010-01-18

    The Institute of Electronics, Information and Communication Engineers

References:  9

Codes

  • NII Article ID (NAID)
    110008004173
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    09135685
  • NDL Article ID
    10554500
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top