ブックマーク問題の近似について

摘要

ハイパーリンクの集合Eで連結されたウェブページの集合Vを表した根付き有向非巡回グラフG=(V,E)を考える．それぞれのノードvは，ユーザがノードvを閲覧するアクセス頻度を持っている．アクセスコストは，根ノードrからあるノードvに到達するためのステップ数の期待値で定義される．ブックマークは，グラフCの根ノードrに付加するショートカットリンクであり，アクセスコストを小さくする効果がある．ブックマーク問題は，アクセスコストを最も改善するようなブックマーク集合を求める問題である．本稿では，ブックマーク問題に対する(1-1/e)近似アルゴリズムを示す．また，NP{is contained in}DTIME (N{sup}(O(log log N)))を満たさない場合には，(1-1/e)よりも良い近似比を持つ多項式時間のアルゴリズムは存在しないことを示す．ここで，Nは入力サイズを表している．