Lower and Upper Bounds for Random Mimimum Satisfiability Problem

DOI10.1007/978-3-319-19647-3_11zbMath1407.68452OpenAlexW1132907863MaRDI QIDQ3452557

Kaile Su, Ping Huang

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

upper boundslower boundsMinSat

Mathematics Subject Classification ID

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

Uses Software

• MiniSat
• MAX-2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• SAT-based MaxSAT algorithms
• Resolution-based lower bounds in MaxSAT
• An upper (lower) bound for Max (Min) CSP
• On approximation algorithms for the minimum satisfiability problem
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• On the lower bounds of random Max 3 and 4-SAT
• Optimizing with minimum satisfiability
• Approximating MIN 2-SAT and MIN 3-SAT
• A tighter upper bound for random MAX \(2\)-SAT
• The scaling window of the 2-SAT transition
• On the maximum satisfiability of random formulas
• The Minimum Satisfiability Problem
• Random MAX SAT, random MAX CUT, and their phase transitions
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Exact MinSAT Solving

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