Randomized greedy: new variants of some classic approximation algorithms

MaRDI QIDQ5365069zbMATH OpenFDO

Authors Kevin P. Costello, Asaf Shapira, Prasad Tetali

Publication date 29 September 2017

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• On randomizing two derandomized greedy algorithms
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• Randomized variants of Johnson's algorithm for MAX SAT
• Theory and Applications of Satisfiability Testing
• On Some Recent Approximation Algorithms for MAX SAT

Cited in

(9)

• On extensions of the deterministic online model for bipartite matching and max-sat
• Using the method of conditional expectations to supply an improved starting point for CCLS
• On the power of random greedy algorithms
• CHAMP: a multipass algorithm for Max Sat based on saver variables
• Go-MOCE: greedy order method of conditional expectations for Max Sat
• 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 variants of Johnson's algorithm for MAX SAT
• On randomizing two derandomized greedy algorithms

This page was built for publication: Randomized greedy: new variants of some classic approximation algorithms

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