Optimal 2-constraint satisfaction via sum-product algorithms

DOI10.1016/J.IPL.2005.11.013MaRDI QIDQ844150zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

algorithmscomputational complexitymatrix multiplicationmaximum satisfiabilitysum-product

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A simplified NP-complete MAXSAT problem
• An Algebraic Model for Combinatorial Problems
• Bucket elimination: A unifying framework for reasoning
• Factor graphs and the sum-product algorithm
• Fast multiplication of large numbers
• Faster exact algorithms for hard problems: A parameterized point of view
• Matrix multiplication via arithmetic progressions
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cited in

(11)

• Improved exact algorithms for mildly sparse instances of MAX SAT
• Solving sparse instances of Max SAT via width reduction and greedy restriction
• Exact and approximation algorithms for the maximum constraint satisfaction problem over the point algebra
• Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Counting solutions to CSP using generating polynomials
• A modeling and computational study of the frustration index in signed networks
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• New exact algorithms for the 2-constraint satisfaction problem
• An LP-Designed Algorithm for Constraint Satisfaction

Describes a project that uses

Uses Software

• MAX-2-SAT

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)