Using the method of conditional expectations to supply an improved starting point for CCLS
From MaRDI portal
Publication:2091119
DOI10.1007/s10878-022-00907-5zbMath1505.90097MaRDI QIDQ2091119
Shahar Golan, Yochai Twitto, Daniel Berend
Publication date: 31 October 2022
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-022-00907-5
combinatorial optimization; local search; maximum satisfiability; method of conditional expectations
90C27: Combinatorial optimization
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- New local search methods for partial MaxSAT
- A multi-restart iterated local search algorithm for the permutation flow shop problem minimizing total flow time
- SAT-based MaxSAT algorithms
- Autocorrelation measures for the quadratic assignment problem
- Local search for Boolean satisfiability with configuration checking and subscore
- Improving configuration checking for satisfiable random \(k\)-SAT instances
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
- The traveling salesman problem and its variations
- Improved exact algorithms for MAX-SAT
- Combining simulated annealing with local search heuristics
- On the classification of NP-complete problems in terms of their correlation coefficient
- Guided local search for solving SAT and weighted MAX-SAT problems
- A refined branching algorithm for the maximum satisfiability problem
- A tutorial on the cross-entropy method
- Experimental results on the crossover point in random 3-SAT
- 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
- Bounds on Greedy Algorithms for MAX SAT
- Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
- Solving (Weighted) Partial MaxSAT through Satisfiability Testing
- Sharp thresholds of graph properties, and the $k$-sat problem
- On the Approximation of Maximum Satisfiability
- New Upper Bounds for Maximum Satisfiability
- Random MAX SAT, random MAX CUT, and their phase transitions
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
- On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem
- The asymptotic k-SAT threshold
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- 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
