Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
verfasst von : Ruiwen Chen, Rahul Santhanam
Erschienen in: Theory and Applications of Satisfiability Testing -- SAT 2015
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We give improved deterministic algorithms solving sparse instances of MAX-SAT and MAX-k-CSP. For instances with n variables and cn clauses (constraints), we give algorithms running in time poly(
n
)·2
n
(1 −
μ
)
for
$\mu = \Omega( {1 \over c} )$
and polynomial space solving MAX-SAT and MAX-
k
-SAT,
$\mu = \Omega({{1}\over{\sqrt{c}}})$
and exponential space solving MAX-SAT and MAX-
k
-SAT,
$\mu = \Omega({{1}\over{ck^2}})$
and polynomial space solving MAX-k-CSP,
$\mu = \Omega({{1}\over{ck^3}})$
and exponential space solving MAX-k-CSP.
The previous MAX-SAT algorithms have savings
$\mu = \Omega({{1} \over{c^2 log^2 c}})$
for running in polynomial space [15] and
$\mu = \Omega({{1} \over{c log c}})$
for exponential space [5]. We also give an algorithm with improved savings for satisfiability of depth-2 threshold circuits with
cn
wires.