MAX 3 - SATに対する高性能近似アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1995-05-12
• タイトル: MAX 3 - SATに対する高性能近似アルゴリズム
• タイトル / 言語: en
• タイトル: An Approximation Algorithm for MAX 3 - SAT
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋大学工学部
• 著者所属: 名古屋大学工学部
• 著者所属: 中央大学理工学部
• 著者所属(英): en
• 著者所属(英): School of Engeneering, Nagoya University
• 著者所属(英): en
• 著者所属(英): School of Engeneering, Nagoya University
• 著者所属(英): en
• 著者所属(英): Department of Information and System Engineering, Chuo University
• 著者名: 小野, 孝男; 平田, 富夫; 浅野, 孝夫
• 著者名(英): Takao, Ono; Tomio, Hirata; Takao, Asano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 最近，GoemansとWilliamsonによってMAX 2?SATに対する画期的な近似アルゴリズムが提案された．このアルゴリズムはMAX 2?SATの条件を緩和して凸計画問題に帰着させるという手法を用いており，0．878という近似度を実現している．この手法はMAX CUTやMAX DICUTにも適用され新しいアルゴリズムが得られているが，その他の問題に対してこの手法が適用できるかどうかについて興味がもたれていた．本論文ではこの手法がMAX 3?SATに対しても適用可能であり，その結果0．770?近似アルゴリズムが得られることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Goemans and Williamson recently presented a new approximation algorithm for MAX 2-SAT. Their algorithm achieves 0.878-approximation by reducing MAX 2-SAT to a convex programming problem with relaxation. They used this reduction to make new algorithms for MAX CUT and MAX DICUT, and it was interesting whether this reduction is applicable to other problems. In this paper we present a 0.770-approximation algorithm for MAX 3-SAT using this reduction.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1995, 号 39(1995-AL-045), p. 25-32, 発行日 1995-05-12
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会