線形符号の最大重みに対する近似アルゴリズム

概要

論文の詳細を見る
線形符号Cが与えられたとき, その最小距離を求める問題は, 符号Cの誤り訂正の限界を知る上で重要である. また, 線形符号C⊆{0, 1}^nとy∈{o, 1}^nが与えられたとき, ベクトルyに最も近い符号語c∈Cを求める問題(最尤復号)は, 符号Cの性能を最大限利用する意味でも応用上極めて重要である. しかし, これら問題はNP-困難であることが知られており, P≠NPである限り, これらに対する効率的なアルゴリズムは存在しない. 本論文では, これらに関連する問題として, 線形符号Cに対する"最大重み:MAX-WEIGHT"について考察する. 最大重みに対して, これまでにMAX-WEIGHT notin PTASが知られているものの, その近似に関する非自明な上界・下界は知られていない. 従って, 本論文では, MAX-WEIGHTの計算量的な位置付け(1) MAX-WEIGHTはAPX完全である. (2) MAX-WEIGHTは2-近似可能である; (3) P bne NPの仮定のもとでMAX- WEIGHT は(10/9)-近似不可能である-を示す.
1999-05-18