zbMATH — the first resource for mathematics

Optimal 2-constraint satisfaction via sum-product algorithms. (English) Zbl 1186.68439
Summary: 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 $$O^{\ast}(nmd^{n\omega/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^{*}(nm1.732^n)$$ time. This improves on a recent result by R. Williams [“A new algorithm for optimal 2-constraint satisfaction and its implications”, Theor. Comput. Sci. 348, No. 2–3, 357–365 (2005; Zbl 1081.68095)] by reducing the polynomial factor from $$nm^{3}$$ to about $$nm$$.

MSC:
 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) 68Q25 Analysis of algorithms and problem complexity
MAX-2-SAT
Full Text:
References:
 [1] Alber, J.; Gramm, J.; Niedermeier, R., Faster exact algorithms for hard problems: a parameterized point of view, Discrete math., 229, 1-3, 3-27, (2001) · Zbl 0973.68256 [2] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. symbolic comput., 9, 3, 791-799, (1990) · Zbl 0702.65046 [3] Cormen, T.H.; Leiserson, C.L.; Rivest, R.L., Introduction to algorithms, (1990), MIT Press Cambridge, MA · Zbl 1158.68538 [4] Dechter, R., Bucket elimination: a unifying framework for reasoning, Artificial intelligence, 113, 1-2, 41-85, (1999) · Zbl 0939.68847 [5] Gramm, J.; Hirsch, E.A.; Niedermeier, R.; Rossmanith, P., Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT, Discrete appl. math., 130, 2, 139-155, (2003) · Zbl 1051.68078 [6] M. Koivisto, Sum – product algorithms for the analysis of genetic risks, PhD thesis, University of Helsinki, January 2004 [7] Kschischang, F.R.; Frey, B.; Loeliger, H.-A., Factor graphs and the sum – product algorithm, IEEE trans. inform. theory, 47, 2, 498-519, (2001) · Zbl 0998.68234 [8] Raman, V.; Ravikumar, B.; Rao, S.S., A simplified NP-complete MAXSAT problem, Inform. process. lett., 65, 1, 1-6, (1998) · Zbl 1339.68122 [9] Schönhage, A.; Strassen, V., Schnelle multiplikation großer zahlen, Computing, 7, 281-292, (1971) · Zbl 0223.68007 [10] Stearns, R.E.; Hunt, H.B., An algebraic model for combinatorial problems, SIAM J. comput., 25, 2, 448-476, (1996) · Zbl 0844.68063 [11] Williams, R., A new algorithm for optimal 2-constraint satisfaction and its implications, Theoret. comput. sci., 348, 2-3, 257-365, (2005) · Zbl 1081.68095 [12] Woeginger, G.J., Exact algorithms for NP-hard problems: A survey, (), 185-207 · Zbl 1024.68529
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.