Probabilistic characterization of random Max \(r\)-Sat
From MaRDI portal
Publication:2042075
DOI10.1016/j.disopt.2021.100630zbMath1506.68120MaRDI 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 optimization; local search; maximum satisfiability; fitness landscapes; autocorrelation length; probabilistic characterization
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
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