Unique Gameの近似困難性について
スポンサーリンク
概要
- 論文の詳細を見る
近年,Clique,MAX-3SAT,Set Coverといった問題の近似値比の限界が示されてきたが,一方,その他多くの問題の限界はまだ未解決である.それらを解決する1つの統一的手法として,グラフの最適化問題であるUnique Gameが研究されている.Unique Gameの難しさに関しては推測がされており,この推測は"Unique Games Conjecture"と呼ばれる.もしこの推測が正しければ,Unique Gameからのリダクションの解析がグラフ問題の近似値比の限界を示す有用な手法になる.本研究では,Unique Gameに対する近似アルゴリズムを実装し,問題を決定する様々な要因について制限した問題を使用することで,ある平行枝がUnique Gameを難しくすることを実験的に見出す.
- 一般社団法人情報処理学会の論文
- 2006-07-03