このアイテムのアクセス数: 283
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| IEICE.ronbun_J81-D1_677.pdf | 495.51 kB | Adobe PDF | 見る/開く |
| タイトル: | NP完全集合によるcoNP集合の近似とその応用について |
| その他のタイトル: | Approximation of coNP Sets by NP-Complete Sets and Its Application |
| 著者: | 宮崎, 修一  岩間, 一雄  |
| 著者名の別形: | Miyazaki, Shuichi Iwama, Kazuo |
| キーワード: | 近似 NP完全集合 coNP集合 例題生成 |
| 発行日: | 25-Jun-1998 |
| 出版者: | 電子情報通信学会 |
| 誌名: | 電子情報通信学会論文誌 |
| 巻: | J81-D1 |
| 号: | 6 |
| 開始ページ: | 677 |
| 終了ページ: | 684 |
| 抄録: | クラスC_1に属する集合L_1が, クラスC_>2に属する集合L_2の部分集合であるとき, L_1はL_2の近似であると言う.L_1⊂L'_1であり, L'_1-L_>1が無限集合となるような近似L'_1が存在しないとき, L_1は最適近似であると言う.C_1がクラスP, C_2がクラスNPである場合には, P≠NPならば弱い条件のもとで最適な近似が存在しないことが示されている.本論文では, C_1がNP完全集合のクラスで, C_2がcoNPである場合に対し, 同様の結果を示す./coNP集合のNP完全集合による近似は, 組合せアルゴリズムを実験的に評価する際の例題生成の効率に深いかかわりをもっている. |
| 著作権等: | © 1998 電子情報通信学会(IEICE) |
| URI: | http://hdl.handle.net/2433/227031 |
| 関連リンク: | http://search.ieice.org/bin/summary.php?id=j81-d1_6_677&category=D&year=1998&lang=J&abst= |
| 出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。