Lower and Upper Bounds for Random Mimimum Satisfiability Problem

DOI10.1007/978-3-319-19647-3_11MaRDI QIDQ3452557zbMATH OpenOpenAlexFDO

Authors Ping Huang, Kaile Su

Publication date 12 November 2015

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-19647-3_11

zbMATH Keywords

lower boundsMinSatupper bounds

Mathematics Subject Classification ID

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

Recommendations

• Probabilistic bounds and algorithms for the maximum satisfiability problem
• The satisfiability threshold for a seemingly intractable random constraint satisfaction problem
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• On the lower bounds of random Max 3 and 4-SAT
• On the Lower Bounds of Random Max 3 and 4-SAT
• scientific article; zbMATH DE number 1775407
• Bounds on threshold of regular random k-SAT
• A tighter upper bound for random MAX \(2\)-SAT
• On the lower bounds of \((1, 0)\)-super solutions for random \(k\)-SAT
• The satisfiability threshold for randomly generated binary constraint satisfaction problems

Cites work

• A tighter upper bound for random MAX \(2\)-SAT
• An upper (lower) bound for Max (Min) CSP
• Approximating MIN 2-SAT and MIN 3-SAT
• Exact MinSAT Solving
• scientific article; zbMATH DE number 5139161 (Why is no real title available?)
• scientific article; zbMATH DE number 734955 (Why is no real title available?)
• scientific article; zbMATH DE number 1448978 (Why is no real title available?)
• On approximation algorithms for the minimum satisfiability problem
• On the lower bounds of random Max 3 and 4-SAT
• On the maximum satisfiability of random formulas
• Optimizing with minimum satisfiability
• Random graphs.
• Random MAX SAT, random MAX CUT, and their phase transitions
• Resolution-based lower bounds in MaxSAT
• SAT-based MaxSAT algorithms
• The Minimum Satisfiability Problem
• The scaling window of the 2-SAT transition
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.

Cited in

(3)

• On the Lower Bounds of Random Max 3 and 4-SAT
• On the performance of MaxSAT and MinSAT solvers on 2SAT-MaxOnes
• An upper (lower) bound for Max (Min) CSP

Describes a project that uses

Uses Software

• MiniSat
• MAX-2-SAT

This page was built for publication: Lower and Upper Bounds for Random Mimimum Satisfiability Problem

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