Optimal 2-constraint satisfaction via sum-product algorithms

"We show that for a given set of m pairwise constraints over n variables, a variable assignment that satisfies maximally many M constraints (MAX-2-CSP) can be found in 0* (nm d(nw/3)) time, where d is the maximum number of states per variable, and omega < 2.376 is the matrix product exponent over a ring; the notation O* suppresses factors polylogarithmic in m and n. As a corollary, MAX-2-SAT can be solved in O*(nm 1.732(n)) time. This improves on a recent result by Williams [R. Williams, A new algorithm for optimal 2-constraint satisfaction and its implications, Theoret. Comput. Sci. 348 (2-3) (2005) 357-365] by reducing the polynomial factor from nm(3) to about nm. (c) 2005 Elsevier B.V. All rights reserved."