Using the method of conditional expectations to supply an improved starting point for CCLS

DOI10.1007/s10878-022-00907-5zbMath1505.90097OpenAlexW4298132557MaRDI 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

zbMATH Keywords

combinatorial optimizationlocal searchmaximum satisfiabilitymethod of conditional expectations

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Uses Software

• Walksat
• Sat4j
• QMaxSAT
• MiniMaxSat
• CCASat
• MaxHS

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

This page was built for publication: Using the method of conditional expectations to supply an improved starting point for CCLS