Minimum and maximum against k lies

Michael Hoffmann, Jiří Matoušek, Yoshio Okamoto, Philipp Zumstein
http://arxiv.org/abs/1002.0562

他の人の論文を読む時間がとれないため，自分の論文を紹介するというよくない傾向．昨日，LAシンポジウムで話した内容です．お聞きいただいた方はお分かりかと思うのですが，話に出てきた内容はこの論文のはじめの4ページまでで，後の7ページぐらいは全部省略です．

比較結果が信用できないときにどうやって最大値と最小値を見つけるのか，という話．「信用できない」のモデルにはいろいろあるけど，ここでは高々k回間違える，というモデルを考えます．このときにMartin Aignerが昔の研究で出した比較回数の上界を改善したというのが主要結果．アルゴリズムのシンプルさが売り．(Aignerのアルゴリズムもシンプルでしたが．)