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

DOI10.1016/j.disopt.2021.100630zbMath1506.68120OpenAlexW3133801428MaRDI 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 optimizationlocal searchmaximum satisfiabilityfitness landscapesautocorrelation lengthprobabilistic characterization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

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

This page was built for publication: Probabilistic characterization of random Max \(r\)-Sat