Go-MOCE: greedy order method of conditional expectations for Max Sat

DOI10.1016/j.disopt.2022.100685OpenAlexW4210699508MaRDI QIDQ2691199

Shahar Golan, Yochai Twitto, Daniel Berend

Publication date: 29 March 2023

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2022.100685

zbMATH Keywords

combinatorial optimizationprobabilistic algorithmsanalysis of algorithmsmaximum satisfiabilitymethod of conditional expectations

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational aspects of satisfiability (68R07)

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
• Unnamed Item
• Unnamed Item
• SAT-based MaxSAT algorithms
• Local search for Boolean satisfiability with configuration checking and subscore
• Improving configuration checking for satisfiable random \(k\)-SAT instances
• A threshold for unsatisfiability
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Dynamic polynomial watchdog encoding for solving weighted MaxSAT
• Guided local search for solving SAT and weighted MAX-SAT problems
• A tutorial on the cross-entropy method
• Experimental results on the crossover point in random 3-SAT
• 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
• 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
• On a combinatorial game

This page was built for publication: Go-MOCE: greedy order method of conditional expectations for Max Sat