Randomized variants of Johnson's algorithm for MAX SAT

MaRDI QIDQ5365070zbMATH OpenFDO

Authors Matthias Poloczek, Georg Schnitger

Publication date 29 September 2017

Full work available at URL http://dl.acm.org/citation.cfm?id=2133087

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Recommendations

• On Some Recent Approximation Algorithms for MAX SAT
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• Randomized greedy: new variants of some classic approximation algorithms
• On randomizing two derandomized greedy algorithms
• Tight bound on Johnson's algorithm for maximum satisfiability

Cited in

(10)

• Tight bound on Johnson's algorithm for maximum satisfiability
• On extensions of the deterministic online model for bipartite matching and max-sat
• Simple approximation algorithms for balanced MAX~2SAT
• A novel algorithm for Max Sat calling MOCE to order
• CHAMP: a multipass algorithm for Max Sat based on saver variables
• An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• Randomized greedy: new variants of some classic approximation algorithms
• Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles
• Simplified tight analysis of Johnson's algorithm

This page was built for publication: Randomized variants of Johnson's algorithm for MAX SAT

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