2014年
Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction.
THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2014
- ,
- ,
- 巻
- 8561
- 号
- 開始ページ
- 32
- 終了ページ
- 47
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- DOI
- 10.1007/978-3-319-09284-3_4
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
We present a moderately exponential time polynomial space algorithm for sparse instances of Max SAT. Our algorithms run in time of the form O(2((1-mu(c))n)) for instances with n variables and cn clauses. Our deterministic and randomized algorithm achieve mu(c) = Omega(1/c(2) log(2) c) and mu(c) = Omega(1/c log(3) c) respectively. Previously, an exponential space deterministic algorithm with mu(c) = Omega(1/c log c) was shown by Dantsin and Wolpert [SAT 2006] and a polynomial space deterministic algorithm with mu(c) = Omega(1/2(O(c))) was shown by Kulikov and Kutzkov [CSR 2007].
Our algorithms have three new features. They can handle instances with (1) weights and (2) hard constraints, and also (3) they can solve counting versions of Max SAT. Our deterministic algorithm is based on the combination of two techniques, width reduction of Schuler and greedy restriction of Santhanam. Our randomized algorithm uses random restriction instead of greedy restriction.
Our algorithms have three new features. They can handle instances with (1) weights and (2) hard constraints, and also (3) they can solve counting versions of Max SAT. Our deterministic algorithm is based on the combination of two techniques, width reduction of Schuler and greedy restriction of Santhanam. Our randomized algorithm uses random restriction instead of greedy restriction.
- リンク情報
-
- DOI
- https://doi.org/10.1007/978-3-319-09284-3_4
- DBLP
- https://dblp.uni-trier.de/rec/conf/sat/SakaiST14
- J-GLOBAL
- https://jglobal.jst.go.jp/detail?JGLOBAL_ID=201402294748617847
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000345595300004&DestApp=WOS_CPL
- URL
- https://dblp.uni-trier.de/conf/sat/2014
- URL
- https://dblp.uni-trier.de/db/conf/sat/sat2014.html#SakaiST14
- ID情報
-
- DOI : 10.1007/978-3-319-09284-3_4
- ISSN : 0302-9743
- DBLP ID : conf/sat/SakaiST14
- J-Global ID : 201402294748617847
- Web of Science ID : WOS:000345595300004