WEKO3
アイテム
MAX SATに対するYannakakisのアルゴリズムの精密化
https://ipsj.ixsq.nii.ac.jp/records/32264
https://ipsj.ixsq.nii.ac.jp/records/3226409633090-2aa3-4f3a-b8e0-da4fe6ac55f1
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL96054011.pdf (732.3 kB)
|
Copyright (c) 1996 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1996-10-17 | |||||||
| タイトル | ||||||||
| タイトル | MAX SATに対するYannakakisのアルゴリズムの精密化 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A Refinement of Yannakakis's Algorithm for MAX SAT | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 中央大学理工学部情報工学科 | ||||||||
| 著者所属 | ||||||||
| 中央大学理工学部情報工学科 | ||||||||
| 著者所属 | ||||||||
| 名古屋大学工学部 | ||||||||
| 著者所属 | ||||||||
| 名古屋大学工学部 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information and System Engineering, Chuo University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information and System Engineering, Chuo University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Engineering, Nagoya University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Engineering, Nagoya University | ||||||||
| 著者名 |
浅野, 孝夫
× 浅野, 孝夫
|
|||||||
| 著者名(英) |
Takao, Asano
× Takao, Asano
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | MAX SAT（充足性最大化問題）とは，節の集合と各節の重みが与えられたとき，充足する節の重みの総和を最大にするような真偽割り当てを求める問題である．この論文ではMAX SATに対するYannakakisの0．75?近似アルゴリズムを精密化したアルゴリズムを与える。精密化されたこのアルゴリズムを従来のアルゴリズムと組み合わせることで近似比0．767のより高性能近似アルゴリズムが得られる。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | MAX SAT (the maximum satisfiability problem) is : given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights o the satisfied clauses. In this paper, we present an approximation algorithm for MAX SAT which is a refinement of Yammakakis's algorithm. This algorithm leads to a better approximation algorithm with performance guarantee 0.767 if it is combined with the previous algorithms for MAX SAT. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1996, 号 100(1996-AL-054), p. 81-88, 発行日 1996-10-17 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
