論文

査読有り
2014年

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

THEORY AND APPLICATIONS OF SATISFIABILITY TESTING - SAT 2014
  • Takayuki Sakai
  • ,
  • Kazuhisa Seto
  • ,
  • Suguru Tamaki

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.

リンク情報
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

エクスポート
BibTeX RIS