CHAMP: a multipass algorithm for Max Sat based on saver variables

DOI10.1016/J.DISOPT.2023.100760MaRDI QIDQ2688471zbMATH OpenOpenAlexFDO

Authors Daniel Berend, Shahar Golan, Yochai Twitto

Publication date 3 March 2023

Published in Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationiterated algorithmlocal searchmaximum satisfiability

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27)

Recommendations

• A Preprocessor for Max-SAT Solvers
• Minimaxsat: an efficient weighted Max-SAT solver
• MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
• scientific article; zbMATH DE number 956866
• New inference rules for Max-SAT

Cites work

• A novel algorithm for Max Sat calling MOCE to order
• A threshold for unsatisfiability
• A tutorial on the cross-entropy method
• Bounds on greedy algorithms for MAX SAT
• CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability
• CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability
• Experimental results on the crossover point in random 3-SAT
• GitHub
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• scientific article; zbMATH DE number 3495588 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 2050711 (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?)
• Improved algorithms for sparse MAX-SAT and MAX-k-CSP
• Minimaxsat: an efficient weighted Max-SAT solver
• New inference rules for Max-SAT
• On a combinatorial game
• On the Approximation of Maximum Satisfiability
• 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
• Randomized variants of Johnson's algorithm for MAX SAT
• SAT-based MaxSAT algorithms
• Sharp thresholds of graph properties, and the k-sat problem
• Solving (Weighted) Partial MaxSAT through Satisfiability Testing
• Solving Satisfiability with Less Searching
• The asymptotic \(k\)-SAT threshold
• The Reactive Tabu Search
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Threshold values of random K‐SAT from the cavity method
• Tight bound on Johnson's algorithm for maximum satisfiability

Cited in

(1)

• On the counting version of the maximum 2-satisfiability problem

Describes a project that uses

Uses Software

• MaxHS
• MiniMaxSat
• Walksat
• Sat4j
• QMaxSAT
• GitHub

This page was built for publication: CHAMP: a multipass algorithm for Max Sat based on saver variables

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