An Empirical Study of MAX-2-SAT Phase Transitions

DOI10.1016/S1571-0653(04)00464-0zbMath1179.68148OpenAlexW2049991966MaRDI QIDQ3439118

Haiou Shen, Han-Tao 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)

Related Items (5)

A tighter upper bound for random MAX \(2\)-SAT ⋮ MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability ⋮ Exact Algorithms for MAX-SAT ⋮ Efficient branch-and-bound algorithms for weighted MAX-2-SAT ⋮ Improving exact algorithms for MAX-2-SAT

Uses Software

• MAX-2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• Algorithms for the maximum satisfiability problem
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• New worst-case upper bounds for SAT
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• The scaling window of the 2-SAT transition
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• New Upper Bounds for Maximum Satisfiability
• Bounding the unsatisfiability threshold of random 3-SAT
• Exact Algorithms for MAX-SAT
• Faster exact algorithms for hard problems: A parameterized point of view

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