On randomizing two derandomized greedy algorithms

DOI10.4310/JOC.2010.V1.N3.A1MaRDI QIDQ547862zbMATH OpenOpenAlexFDO

Authors Kevin P. Costello, Asaf Shapira, Prasad Tetali

Publication date 27 June 2011

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4310/joc.2010.v1.n3.a1

zbMATH Keywords

randomized algorithmsapproximation algorithms, random graphs

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Recommendations

• On the power of random greedy algorithms
• On the greedy algorithm with random costs
• Randomized greedy: new variants of some classic approximation algorithms
• A note on the random greedy independent set algorithm
• Randomized and derandomized algorithms
• scientific article; zbMATH DE number 780783
• On two random search problems
• On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
• Randomized algorithms in combinatorial optimization: A survey

Cited in

(4)

• Randomized greedy: new variants of some classic approximation algorithms
• On the power of random greedy algorithms
• Solving the weighted MAX-SAT problem using the dynamic convexized method
• Randomized variants of Johnson's algorithm for MAX SAT

This page was built for publication: On randomizing two derandomized greedy algorithms

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