Survey Propagation Inspired Algorithms for Satisfiability

In this note we develop generalized Survey Propagation (SP) equations from the cavity method. We quantize the message space of the messages to develop a message passing rule. We investigate a framework of greedy algorithms for finding out satisfying assignment inspired by the new SP rule. We show that the recent Hajiaghayi-Sorkin algorithm for satisfiability is a special case in this framework of algorithms and the lower bound on the conjectured threshold given by the Hajiaghayi-Sorkin algorithm can be improved. This improvement is shown by experiments.


Year:
2008
Keywords:
Laboratories:




 Record created 2008-02-04, last modified 2018-01-28


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)