Probabilistic characterization of random Max \(r\)-Sat
From MaRDI portal
Publication:2042075
DOI10.1016/j.disopt.2021.100630zbMath1506.68120OpenAlexW3133801428MaRDI QIDQ2042075
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
combinatorial optimizationlocal searchmaximum satisfiabilityfitness landscapesautocorrelation lengthprobabilistic characterization
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
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
