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

DOI10.1016/J.DISOPT.2022.100685MaRDI QIDQ2691199zbMATH OpenOpenAlexFDO

Authors Daniel Berend, Shahar Golan, Yochai Twitto

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 optimizationanalysis of algorithmsprobabilistic algorithmsmaximum satisfiabilitymethod of conditional expectations

Mathematics Subject Classification ID

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

Recommendations

• A novel algorithm for Max Sat calling MOCE to order
• Bounds on greedy algorithms for MAX SAT
• The probabilistic analysis of a greedy satisfiability algorithm
• scientific article; zbMATH DE number 1947423
• A taxonomy of exact methods for partial Max-SAT
• A new greedy randomised adaptive search procedure for solving the maximum satisfiability problem
• An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT
• On the greedy algorithm for satisfiability
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• Generalizing Core-Guided Max-SAT

Cites work

• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1301967 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• scientific article; zbMATH DE number 956863 (Why is no real title available?)
• A threshold for unsatisfiability
• A tutorial on the cross-entropy method
• Bounds on greedy algorithms for MAX SAT
• CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability
• Dynamic polynomial watchdog encoding for solving weighted MaxSAT
• Experimental results on the crossover point in random 3-SAT
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• Guided local search for solving SAT and weighted MAX-SAT problems
• Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP
• Improving configuration checking for satisfiable random \(k\)-SAT instances
• Local search for Boolean satisfiability with configuration checking and subscore
• Minimaxsat: an efficient weighted Max-SAT solver
• New inference rules for Max-SAT
• On a combinatorial game
• On the Approximation of Maximum Satisfiability
• On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Proof of the satisfiability conjecture for large \(k\)
• QMaxSAT: A partial Max-SAT solver
• Random MAX SAT, random MAX CUT, and their phase transitions
• Randomized greedy: new variants of some classic approximation algorithms
• SAT-based MaxSAT algorithms
• Sharp thresholds of graph properties, and the $k$-sat problem
• Solving (Weighted) Partial MaxSAT through Satisfiability Testing
• Some optimal inapproximability results
• Stochastic local search. Foundations and applications.
• The asymptotic \(k\)-SAT threshold
• The first and second Max-SAT evaluations
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Threshold values of random K‐SAT from the cavity method

Cited in

(1)

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

Describes a project that uses

Uses Software

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2691199)