Average-case analysis for the MAX-2SAT problem

DOI10.1016/J.TCS.2009.12.020MaRDI QIDQ964385zbMATH OpenOpenAlexFDO

Authors Osamu Watanabe, Masaki Yamamoto

Publication date 15 April 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.12.020

zbMATH Keywords

average case analysisbelief propagationMAX-2SATplanted solution model

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Recommendations

• Average-Case Analysis for the MAX-2SAT Problem
• A Spectral Method for MAX2SAT in the Planted Solution Model
• Approximating highly satisfiable random 2-SAT
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Local maxima and improved exact algorithm for MAX-2-SAT

Cites work

• Experimental and Efficient Algorithms
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• Generating instances for MAX2SAT with optimal solutions
• scientific article; zbMATH DE number 1708072 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1796992 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 2243408 (Why is no real title available?)
• Some optimal inapproximability results

Cited in

(5)

• Generating instances for MAX2SAT with optimal solutions
• Message passing algorithms for MLS-3LIN problem
• Finding Most Likely Solutions
• Average-Case Analysis for the MAX-2SAT Problem
• Finding most likely solutions

This page was built for publication: Average-case analysis for the MAX-2SAT problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q964385)