Email Gateway (May 02 2024 at 15:19): Email Gateway (May 02 2024 at 15:19):From: Manuel Eberl <manuel@pruvisto.org>
Another entry on randomised (or in this case de-randomised) algorithms
by Emin Karayel!
Derandomization with Conditional Expectations
by Emin Karayel
The Method of Conditional Expectations (sometimes also called "Method of
Conditional Probabilities") is one of the prominent derandomization
techniques. Given a randomized algorithm, it allows the construction of
a deterministic algorithm with a result that matches the average-case
quality of the randomized algorithm. Using this technique, this entry
starts with a simple example, an algorithm that obtains a cut that
crosses at least half of the edges. This is a well-known approximate
solution to the Max-Cut problem. It is followed by a more complex and
interesting result: an algorithm that returns an independent set
matching (or exceeding) the Caro-Wei bound:
where is the vertex count and is the average degree of the graph. Both
algorithms are efficient and deterministic, and follow from the
derandomization of a probabilistic existence proof.
https://www.isa-afp.org/entries/Derandomization_Conditional_Expectations.html
Enjoy,
Manuel
Last updated: Jan 04 2025 at 20:18 UTC