Timeline for What is the easiest randomized algorithm to motivate to the layperson?
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 10, 2010 at 10:11 | comment | added | Louigi Addario-Berry | Well, it depends on who it is supposed to be non-trivial to. I think the greedy procedure is harder to explain to a layperson than the random one. Also, I imagine the layperson who has a hard time with Markov is also unlikely to be raising questions about efficiency when you give them the existence proof. But it's true that it isn't exact. | |
| Sep 10, 2010 at 5:23 | comment | added | miforbes | I know I'm being picky here, but I suppose I'm looking for an algorithm to solve a problem exactly. But further, I don't consider the "derandomized" 2-approximation algorithm for max-cut to be non-trivial - it is just a greedy/conditional-expectation result. (also, the randomized algorithm shows existence apriori, and to get efficiency we need a Markov-type result; not hard but not easily to explain to a layperson) | |
| Sep 10, 2010 at 0:39 | history | answered | Louigi Addario-Berry | CC BY-SA 2.5 |