On randomizing two derandomized greedy algorithms

DOI10.4310/JOC.2010.V1.N3.A1zbMATH Open1244.68084OpenAlexW2329544464MaRDI QIDQ547862FDOQ547862

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

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
• scientific article; zbMATH DE number 7378726
• Randomized algorithms in combinatorial optimization: A survey

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)

Cited In (4)

• Randomized variants of Johnson's algorithm for MAX SAT
• 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

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)