Optimal 2-constraint satisfaction via sum-product algorithms

DOI10.1016/j.ipl.2005.11.013zbMath1186.68439MaRDI 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

algorithms; computational complexity; maximum satisfiability; matrix multiplication; sum-product

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

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, Improved exact algorithms for mildly sparse instances of MAX SAT, Counting solutions to CSP using generating polynomials, Solving SCS for bounded length strings in fewer than \(2^n\) steps, Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP

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