| 講演名 | 1999/5/18 線形符号の最大重みに対する近似アルゴリズム 伊東 利哉, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 線形符号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)-近似不可能である-を示す. |
| 抄録(英) | The minimum distance of a linear code C is a useful metric property for estimating the error correction upper bound of C and the maximum likelihood decoding of a linear code C is also of practical and theoretical importance. These problems are known to be NP-hard and are NP-hard to approximate within any constant factor to the optimum. As a problem related to the above, we consider the maximization problem MAX-WEIGHT: Given a generating matrix of a linear code C, find a codeword c∈C with its weight as close to the maximum weight of C as possible. It is shown that MAX-WEIGHT notin PTAS unless P = NP, however, no nontrivial approximation upper and lower bounds are known. In this paper, we investigate the complexity of MAX-WEIGHT to make the approximation upper and lower bounds more precise, and then show that (1) MAX-WEIGHT is APX-compete; (2) MAX-WEIGHT is 2-approximable; and (3) MAX-WEIGHT is not (10/9)-approximable unless P = NP. |
| キーワード(和) | 近似アルゴリズム / APX-完全 / 最大重み / 線形符号 |
| キーワード(英) | Approximation Algorithms / APX-complete / Maximum Weight / Linear Codes |
| 資料番号 | IT99-10 |
| 発行日 |
| 研究会情報 | |
| 研究会 | IT |
|---|---|
| 開催期間 | 1999/5/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Theory (IT) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 線形符号の最大重みに対する近似アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Approximating the maximum Weight of Linear Codes is APX-complete |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 近似アルゴリズム / Approximation Algorithms |
| キーワード(2)（和/英） | APX-完全 / APX-complete |
| キーワード(3)（和/英） | 最大重み / Maximum Weight |
| キーワード(4)（和/英） | 線形符号 / Linear Codes |
| 第 1 著者 氏名（和/英） | 伊東 利哉 / TOSHIYA ITOH |
| 第 1 著者 所属（和/英） | 東京工業大学 大学院総合理工学研究科 物理情報システム創造専攻 Department of Information Processing Interdisciplinary Graduate School of Science and Engineering Tokyo Institute of Technology |
| 発表年月日 | 1999/5/18 |
| 資料番号 | IT99-10 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 56 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |