MAX SATに対する近似アルゴリズムの実際的評価

• Item type: SIG Technical Reports(1)
• 公開日: 1998-03-20
• タイトル: MAX SATに対する近似アルゴリズムの実際的評価
• タイトル / 言語: en
• タイトル: Practical Performances of Approximation Algorithms 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
• 著者名: 堀, 邦彰; 浅野, 孝夫
• 著者名(英): Kuniaki, Hori; Takao, Asano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: MAX SAT（最大充足化問題）とは，重み付きクローズ集合が与えられたときに，満たされるクローズの重みの和が最大となるような真偽割当を見つけ出す問題である．本論文は今までに提案されているいくつかの近似アルゴリズムをプログラム化し，計算機実験を通してその理論的性能と実際的性能を比較，考察したものである．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: MAX SAT (the maximum satisfiability problem) is stated as follows: given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of satisfied clauses. In this paper, we implement several exisiting approximation algorithms and compare their theoretical and practical performances.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1998, 号 28(1997-AL-061), p. 23-30, 発行日 1998-03-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会