A Spectral Method for MAX2SAT in the Planted Solution Model

DOI10.1007/978-3-540-77120-3_12zbMath1193.68295OpenAlexW1516897638MaRDI QIDQ5387750

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
• Solving random satisfiable 3CNF formulas in expected polynomial time
• Why Almost All k-Colorable Graphs Are Easy
• Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
• An Adaptive Spectral Heuristic for Partitioning Random Graphs
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Some optimal inapproximability results
• Mathematical Foundations of Computer Science 2005
• Average-Case Analysis for the MAX-2SAT Problem
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

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