Optimal 2-constraint satisfaction via sum-product algorithms

DOI10.1016/j.ipl.2005.11.013zbMath1186.68439OpenAlexW2168696918MaRDI QIDQ844150

Mikko Koivisto

Publication date: 18 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.11.013

zbMATH Keywords

algorithmscomputational complexitymaximum satisfiabilitymatrix multiplicationsum-product

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (7)

Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ A modeling and computational study of the frustration index in signed networks ⋮ A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ Counting solutions to CSP using generating polynomials ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps

Uses Software

• MAX-2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• A simplified NP-complete MAXSAT problem
• Matrix multiplication via arithmetic progressions
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Bucket elimination: A unifying framework for reasoning
• Fast multiplication of large numbers
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Factor graphs and the sum-product algorithm
• An Algebraic Model for Combinatorial Problems
• Faster exact algorithms for hard problems: A parameterized point of view

This page was built for publication: Optimal 2-constraint satisfaction via sum-product algorithms