WEKO3
アイテム
An Approximation Algorithm for MAX 3SAT
https://ipsj.ixsq.nii.ac.jp/records/13564
https://ipsj.ixsq.nii.ac.jp/records/13564ecc6e482-1d12-43a2-9d15-f89452c2ca7d
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL3710002.pdf (442.5 kB)
|
Copyright (c) 1996 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1996-10-15 | |||||||
| タイトル | ||||||||
| タイトル | An Approximation Algorithm for MAX 3SAT | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | An Approximation Algorithm for MAX 3SAT | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 論文 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| その他タイトル | ||||||||
| その他のタイトル | アルゴリズム理論 | |||||||
| 著者所属 | ||||||||
| School of Engineering Nagoya University | ||||||||
| 著者所属 | ||||||||
| School of Engineering Nagoya University | ||||||||
| 著者所属 | ||||||||
| Department of Information and System Engineering Chuo University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Engineering, Nagoya University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Engineering, Nagoya University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information and System Engineering, Chuo University | ||||||||
| 著者名 |
Takao, Ono
× Takao, Ono
|
|||||||
| 著者名(英) |
Takao, Ono
× Takao, Ono
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In this paper we present a 0.769-approximation algorithm for MAX 3SAT. It is a restricted version of MAX SAT in which every clause has at most three literals. The best previously know approximation algorithm for MAX SAT had 0.755-approximation ratio which was given by Goemans and Williamson. Thus we make a slight improvement by limiting MAX SAT to MAX 3SAT. Since approximating MAX 3SAT within 38/39 is NP-complete our result means that the best approximation ratio is between 0.769 and 38/39. | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In this paper we present a 0.769-approximation algorithm for MAX 3SAT. It is a restricted version of MAX SAT, in which every clause has at most three literals. The best previously know approximation algorithm for MAX SAT had 0.755-approximation ratio, which was given by Goemans and Williamson. Thus, we make a slight improvement by limiting MAX SAT to MAX 3SAT. Since approximating MAX 3SAT within 38/39 is NP-complete, our result means that the best approximation ratio is between 0.769 and 38/39. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN00116647 | |||||||
| 書誌情報 |
情報処理学会論文誌 巻 37, 号 10, p. 1760-1764, 発行日 1996-10-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7764 | |||||||
