Probabilistic characterization of random Max \(r\)-Sat

DOI10.1016/j.disopt.2021.100630zbMath1506.68120MaRDI QIDQ2042075

Yochai Twitto, Daniel Berend

Publication date: 27 July 2021

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2021.100630

zbMATH Keywords

combinatorial optimization; local search; maximum satisfiability; fitness landscapes; autocorrelation length; probabilistic characterization

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C27: Combinatorial optimization

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

Uses Software

• UBCSAT
• Walksat
• MiniMaxSat
• MaxHS
• CCLS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• SAT-based MaxSAT algorithms
• Autocorrelation measures for the quadratic assignment problem
• Autocorrelation coefficient for the graph bipartitioning problem
• Exploiting the deep structure of constraint problems
• On the classification of NP-complete problems in terms of their correlation coefficient
• A tutorial on the cross-entropy method
• The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
• Proof of the Satisfiability Conjecture for Large k
• CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability
• Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
• Sharp thresholds of graph properties, and the $k$-sat problem
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The asymptotic k-SAT threshold
• Some optimal inapproximability results
• Threshold values of random K‐SAT from the cavity method
• Theory and Applications of Satisfiability Testing
• On a combinatorial game
• On the landscape ruggedness of the quadratic assignment problem