このアイテムのアクセス数: 2

このアイテムのファイル:
ファイル 記述 サイズフォーマット 
IEICE.ronbun_J81-D1_677.pdf495.51 kBAdobe PDF見る/開く
タイトル: NP完全集合によるcoNP集合の近似とその応用について
その他のタイトル: Approximation of coNP Sets by NP-Complete Sets and Its Application
著者: 宮崎, 修一  kyouindb  KAKEN_id
岩間, 一雄  KAKEN_name
著者名の別形: 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=
出現コレクション:学術雑誌掲載論文等

アイテムの詳細レコードを表示する

Export to RefWorks


出力フォーマット 


このリポジトリに保管されているアイテムはすべて著作権により保護されています。