A Spectral Method for MAX2SAT in the Planted Solution Model

DOI10.1007/978-3-540-77120-3_12MaRDI QIDQ5387750zbMATH OpenOpenAlexFDO

Authors Masaki Yamamoto

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77120-3_12

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• A taxonomy of exact methods for partial Max-SAT
• MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• A new algorithm for parameterized MAX-SAT
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• scientific article; zbMATH DE number 1552232
• scientific article; zbMATH DE number 1629855
• An efficient solver for weighted Max-SAT
• scientific article; zbMATH DE number 1500507
• Improved exact algorithms for mildly sparse instances of MAX SAT

Cites work

• A spectral heuristic for bisecting random graphs
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Algorithms for graph partitioning on the planted partition model
• An Adaptive Spectral Heuristic for Partitioning Random Graphs
• Average-Case Analysis for the MAX-2SAT Problem
• Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• scientific article; zbMATH DE number 2079359 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2005
• Solving random satisfiable 3CNF formulas in expected polynomial time
• Some optimal inapproximability results
• Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
• Why Almost All k-Colorable Graphs Are Easy

Cited in

(2)

• Average-Case Analysis for the MAX-2SAT Problem
• Average-case analysis for the MAX-2SAT problem

This page was built for publication: A Spectral Method for MAX2SAT in the Planted Solution Model

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