文献

J-GLOBAL ID：201502229638017527   整理番号：15A0268944

最大充足可能性問題の疎な例題に対する厳密アルゴリズム

Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction

著者 (1件)： 脊戸和寿 (成蹊大 理工)
資料名： 成蹊大学理工学研究報告  (成けい大学理工学研究報告)
巻： 51  号： 2  ページ： 19-21  発行年： 2014年12月01日 
JST資料番号： F0423A  ISSN： 1880-2265  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 最大充足可能性問題(MaxSAT)とは,入力として与えられる節集合に対して,充足可能な節の最大数を求める問題である。節とはリテラルの論理和であり,リテラルとはブール変数とその否定である。また各節が高々k個のリテラルしか含まないものをMax k-SATと呼び,これらの問題は代表的なNP困難問題の1つである。n変数,m節からなるMaxSATのインスタンスが与えられたとき,O(m2ⁿ)時間で解ける。著者等の目標は,MaxSATをある絶対定数μ>0に対して,O(poly(m)2^(1-μ)n)時間で解くことであるが,mに制限がないと困難なのでm=cnに制限した疎な問題に焦点をあてた。既に報告されているアルゴリズムに改良を加えて,μ(c)=Ω(1/c²log²c)の多項式領域アルゴリズムを与えて,計算時間を求めるアルゴリズムを提示した。

シソーラス用語： *充足可能性問題 ,  問題 ,  *機能 ,  *操作 ,  アルゴリズム ,  CPU時間 ,  近似法
準シソーラス用語： NP困難問題 ,  計算アルゴリズム ,  計算時間 ,  *最大化 ,  疎近似

分類 (1件)： 数値計算  (JE02000J)

タイトルに関連する用語 (2件)： 充足可能性問題 ,  厳密アルゴリズム