Optimal 2-constraint satisfaction via sum-product algorithms
From MaRDI portal
Publication:844150
DOI10.1016/J.IPL.2005.11.013zbMATH Open1186.68439OpenAlexW2168696918MaRDI QIDQ844150FDOQ844150
Authors: 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
Recommendations
- Automata, Languages and Programming
- A new algorithm for optimal 2-constraint satisfaction and its implications
- New exact algorithms for the 2-constraint satisfaction problem
- New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree
- An LP-Designed Algorithm for Constraint Satisfaction
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fast multiplication of large numbers
- Matrix multiplication via arithmetic progressions
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A simplified NP-complete MAXSAT problem
- Factor graphs and the sum-product algorithm
- Bucket elimination: A unifying framework for reasoning
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- Faster exact algorithms for hard problems: A parameterized point of view
- An Algebraic Model for Combinatorial Problems
Cited In (11)
- A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
- A modeling and computational study of the frustration index in signed networks
- New exact algorithms for the 2-constraint satisfaction problem
- Solving sparse instances of Max SAT via width reduction and greedy restriction
- Counting solutions to CSP using generating polynomials
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP
- Exact and approximation algorithms for the maximum constraint satisfaction problem over the point algebra
- Solving SCS for bounded length strings in fewer than \(2^n\) steps
- Improved exact algorithms for mildly sparse instances of MAX SAT
- An LP-Designed Algorithm for Constraint Satisfaction
Uses Software
This page was built for publication: Optimal 2-constraint satisfaction via sum-product algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q844150)
