Average-Case Analysis for the MAX-2SAT Problem

DOI10.1007/11814948_27MaRDI QIDQ5756558zbMATH OpenOpenAlexFDO

Authors Osamu Watanabe, Masaki Yamamoto

Publication date 4 September 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11814948_27

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

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.
• New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree

Cited in

(6)

• Optimal testing for planted satisfiability problems
• Generating weighted MAX-2-SAT instances with frustrated loops: an RBM case study
• A Spectral Method for MAX2SAT in the Planted Solution Model
• Finding Most Likely Solutions
• Finding most likely solutions
• Average-case analysis for the MAX-2SAT problem

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 Q5756558)