.png){kind=icon}
.png){kind=icon}
Return
Warning Propagation Algorithm for the MAX-3-SAT Problem
.png){kind=icon}
PRE
AI
DOI：10.1109/TETC.2017.2736504.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Message propagation algorithms are widely used in approximate inference e.g. Cyber-Social Data Processing and Intelligence Mining. Especially, these algorithms enable hard region become narrower and thus they are very effective in solving satisfiability problems. Warning Propagation algorithm is one kind of basic message propagation algorithms. Based on this Warning Propagation algorithm, we designed a WPY algorithm to solve the MAX-3-SAT problem. We obtained a set of stable warning information, and the value of the partial variable is decided by using the stable set with high probability. Finally, the experiment results show that the WPY algorithm can effectively solve the random MAX-3-SAT instances.
Keywords:
Algorithm design and analysis
Approximation algorithms
Convergence
Heuristic algorithms
Inference algorithms
Software algorithms
Computer science
Warning propagation algorithm
maximum satisfiability problems
factor graph
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
5.4
Papers:
1.1K
Citations:
3.4K