WEKO3
アイテム
An Improvement of Yannakaki's Algorithm for MAX SAT
https://doi.org/10.24789/00001241
https://doi.org/10.24789/000012410cc7ad74-5116-407e-bbf6-903ea3b1677a
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
本文を見る(PDFファイル) (260.7 kB)
|
|
| Item type | 紀要論文 / Departmental Bulletin Paper(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2012-10-01 | |||||||
| タイトル | ||||||||
| タイトル | An Improvement of Yannakaki's Algorithm for MAX SAT | |||||||
| 言語 | en | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | departmental bulletin paper | |||||||
| ID登録 | ||||||||
| ID登録 | 10.24789/00001241 | |||||||
| ID登録タイプ | JaLC | |||||||
| 著者 |
ASANO, Takao
× ASANO, Takao
|
|||||||
| 著者別名 | ||||||||
| 識別子Scheme | WEKO | |||||||
| 識別子 | 23438 | |||||||
| 姓名 | 浅野, 孝夫 | |||||||
| 抄録 | ||||||||
| 内容記述タイプ | Abstract | |||||||
| 内容記述 | MAX SAT(maximum satisfiability problem) is stated as fllows: given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of the satisfied clauses. In this paper, we consider approximation algorithms for MAX SAT proposed by Yannakakis and Goemans-Williamson and present an approximation algorithm which is an improvement of Yannakakis’ alforithm. Althoufh Yannakakis’ original algoritm has no better perfoemance guarantee than Goemans-Williamson, our improved algorithm has a better performance guarantee and leads to a 0.770-approximation algorithm. | |||||||
| 内容記述 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 【査読有】 | |||||||
| 書誌情報 |
中央大学理工学研究所論文集 巻 9, p. 57-77, 発行日 2004-03-31 |
|||||||
| 出版者 | ||||||||
| 出版者 | 中央大学理工学研究所 | |||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1343-0068 | |||||||
| 権利 | ||||||||
| 権利情報 | この資料の著作権は、資料の著作者または学校法人中央大学に帰属します。著作権法が定める私的利用・引用を超える使用を希望される場合には、掲載誌発行部局へお問い合わせください。 | |||||||
| フォーマット | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | application/pdf | |||||||
| 著者版フラグ | ||||||||
| 出版タイプ | VoR | |||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||
