Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction
Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction
复制标题
通过宽度缩减和贪婪限制解决 Max SAT 的稀疏实例
DOI：
10.1007/s00224-014-9600-6
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Suguru Tamaki
中科院分区：
文献类型：
--
作者：
Takayuki Sakai;Kazuhisa Seto;Suguru Tamaki
针对Max SAT稀疏实例，我们提出了一种中等指数的时间和多项式空间算法。对于具有n个变量和cnn子句的实例，我们的算法在时间上运行。我们的确定性算法和随机化算法分别实现了。以前，Dantsin和Wolpert[SAT 2006]提出了指数型空间确定性算法，Kulikov和Kutzkov提出了多项式空间确定性算法[CSR[2007]]。我们的算法有三个新功能。它们可以处理具有(1)权重和(2)硬约束的实例，并且(3)它们可以求解Max SAT的计数版本。我们的确定性算法是基于两种技术的结合，即舒勒的宽度缩减和SanThanam的贪婪限制。我们的随机化算法使用了随机约束而不是贪婪约束。
We present a moderately exponential time and polynomial space algorithm for sparse instances of Max SAT. Our algorithms run in time of the formfor instances withnvariables andcnclauses. Our deterministic and randomized algorithm achieveandrespectively. Previously, an exponential space deterministic algorithm withwas shown by Dantsin and Wolpert [SAT 2006] and a polynomial space deterministic algorithm withwas 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.