Optimal 2-constraint satisfaction via sum-product algorithms
From MaRDI portal
Publication:844150
DOI10.1016/j.ipl.2005.11.013zbMath1186.68439MaRDI QIDQ844150
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
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
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