パラメータ化されたチェルノフ境界を利用した簡略化アルゴリズム分析

本論文では、パラメータ化されたチェルノフ境界を導出し、著名な確率アルゴリズムやデータ構造の分析を簡略化するための応用を示します。我々が提供するパラメータ化されたチェルノフ境界は、指数の定数と平均からの相対的距離との関係のクリーンな定式化において、確率境界が2の冪になることを示します。さらに、これらの境界を用いてハッシュテーブル、ランダムルーティング、およびフロイド・リベスト選択アルゴリズムの簡略化された非再帰的適応に関する新しい分析を提供します。