WEKO3
アイテム
摂動法によるMAX SAT近似アルゴリズムの改良
http://hdl.handle.net/2237/12667
http://hdl.handle.net/2237/1266722843f3b-3954-41d2-8bea-b9631fab0c5a
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
j81-d1_9_1107.pdf (308.0 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2010-02-10 | |||||
| タイトル | ||||||
| タイトル | 摂動法によるMAX SAT近似アルゴリズムの改良 | |||||
| 言語 | ja | |||||
| その他のタイトル | ||||||
| その他のタイトル | Improvement of MAX SAT Approximation Algorithm with Perturbation | |||||
| 言語 | en | |||||
| 著者 |
小野, 孝男
× 小野, 孝男× 平田, 富夫× 浅野, 孝夫 |
|||||
| アクセス権 | ||||||
| アクセス権 | open access | |||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||
| 権利 | ||||||
| 言語 | en | |||||
| 権利情報 | Copyright 1998 IEICE | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | 近似アルゴリズム | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | 充足最大化問題 | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | 摂動 | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | 確率アルゴリズム | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | 充足最大化問題(MAX SAT)とは正の重みの付いた節の集合が与えられたときに，充足する節の重みの和を最大にする変数への真理値の割当てを求める問題である．本論文では MAX SATに対してJohnsonのアルゴリズムとGoemans-Williamsonの近似アルゴリズムを組み合わせた近似アルゴリズムを考え，得られる解に摂動を加えることで0.7685-近似アルゴリズムが得られることを示す． | |||||
| 言語 | ja | |||||
| 出版者 | ||||||
| 出版者 | 電子情報通信学会 | |||||
| 言語 | ja | |||||
| 言語 | ||||||
| 言語 | jpn | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | journal article | |||||
| 出版タイプ | ||||||
| 出版タイプ | VoR | |||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
| 関連情報 | ||||||
| 関連タイプ | isVersionOf | |||||
| 識別子タイプ | URI | |||||
| 関連識別子 | http://www.ieice.org/jpn/trans_online/index.html | |||||
| ISSN | ||||||
| 収録物識別子タイプ | PISSN | |||||
| 収録物識別子 | 0915-1915 | |||||
| 書誌情報 |
ja : 電子情報通信学会論文誌 巻 J81-D, 号 9, p. 1107-1111, 発行日 1998-09-20 |
|||||
| フォーマット | ||||||
| 値 | application/pdf | |||||
| 著者版フラグ | ||||||
| 値 | publisher | |||||
| URI | ||||||
| 識別子 | http://hdl.handle.net/2237/12667 | |||||
| 識別子タイプ | HDL | |||||
| URI | ||||||
| 識別子 | http://www.ieice.org/jpn/trans_online/index.html | |||||
| 識別子タイプ | URI | |||||
