Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MAX-K-CSP:
Reports tagged with max-k-csp:
TR15-112 | 16th July 2015
Ruiwen Chen, Rahul Santhanam

#### Improved Algorithms for Sparse MAX-SAT and MAX-$k$-CSP

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)\cdot 2^{n(1-\mu)}$ for
\begin{itemize}
\item $\mu = \Omega(\frac{1}{c} )$ and polynomial space solving MAX-SAT and MAX-$k$-SAT,
\item $\mu = \Omega(\frac{1}{\sqrt{c}} )$ and ... more >>>

ISSN 1433-8092 | Imprint