An Empirical Study of MAX-2-SAT Phase Transitions

DOI10.1016/S1571-0653(04)00464-0MaRDI QIDQ3439118zbMATH OpenOpenAlexFDO

Authors Haiou Shen, Hantao Zhang

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s1571-0653(04)00464-0

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Random MAX SAT, random MAX CUT, and their phase transitions
• scientific article; zbMATH DE number 2079360
• Exact algorithms for MAX-SAT
• The scaling window of the 2-SAT transition
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cites work

• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A threshold for unsatisfiability
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• Algorithms for the maximum satisfiability problem
• Approximation algorithms for NP-hard problems.
• Bounding the unsatisfiability threshold of random 3-SAT
• Exact algorithms for MAX-SAT
• Faster exact algorithms for hard problems: A parameterized point of view
• scientific article; zbMATH DE number 437557 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 2079360 (Why is no real title available?)
• scientific article; zbMATH DE number 1500507 (Why is no real title available?)
• scientific article; zbMATH DE number 1522934 (Why is no real title available?)
• New Upper Bounds for Maximum Satisfiability
• New worst-case upper bounds for SAT
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• The scaling window of the 2-SAT transition
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cited in

(12)

• A tighter upper bound for random MAX \(2\)-SAT
• MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
• Phase transitions of PP-complete satisfiability problems. (Abstract)
• SAT Distributions with Phase Transitions between Decision and Optimization Problems
• scientific article; zbMATH DE number 2079360 (Why is no real title available?)
• scientific article; zbMATH DE number 2084703 (Why is no real title available?)
• Phase Transition for Maximum Not-All-Equal Satisfiability
• scientific article; zbMATH DE number 1369843 (Why is no real title available?)
• Random MAX SAT, random MAX CUT, and their phase transitions
• Exact algorithms for MAX-SAT
• Efficient branch-and-bound algorithms for weighted MAX-2-SAT
• Improving exact algorithms for MAX-2-SAT

Describes a project that uses

Uses Software

• MAX-2-SAT

This page was built for publication: An Empirical Study of MAX-2-SAT Phase Transitions

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