📊 Answers and discussions for this week's we(a)ekly quiz on greedy algorithms.
Remember: greedy's only a sin if you *forget* to try it!
1/
Greedy #algorithms can be surprisingly powerful, on top of being very often quite intuitive and natural. (Of course, sometimes their *analysis* can be complicated... but hey, you do the analysis only once, but run the algo forever after!)
Let's have a look at a few examples.
2/
Q1 asked about which problem was *not* (known to) have an efficient, optimal greedy solution.
53.6% of you got it right: Set Cover. Well, one reason is because it's NP-hard, so that doesn't help (greedy or not)...
en.wikipedia.org/wiki/Set_cover…
3/
... on the other hand, the Greedy algo for Set Cover does achieve a (log n)-approximation ratio, which is... something? Also, something optimal, assuming P≠NP. So, even then: not so bad!
📝 pages.cs.wisc.edu/~shuchi/course… (PDF)
As for the others: Minimum Spanning Tree (MST) can...
4/
... be solved by Prim's or Kruskal's algorithms (both greedy), and Shortest Path (non-negative weights!) by Dijkstra's algorithm (greedy, too).
OK, let's look at another NP-Hard problem: Vertex Cover. "Given a graph G, gimme a small set of vertices covering every edge of G."
5/
19.6% of you answered Q2 correctly: that simple greedy algorithm doesn't solve VC exactly (hey, it's NP-Hard! 🧐), and does not provide a constant-factor approximation... bummer.
But it still provides a Θ(log n)-approx ratio. Not bad, still! And...
6/
... moreover, there *is* a 2-approximation possible via a greedy algorithm! (and no <1.36-approx unless P=NP).
Using a different greedy algo: one for maximal matching. But it counts! It's greedy! It's simple!
7/
At this point, I should have convinced that greed is good (if you weren't already).
But let's look at our 3rd question: Knapsack! Also NP-Hard, so it'll be about finding a "good enough" (approximation) solution.
BTW, I'd like to understand what's a knapsack (vs. backpack).
8/
So, the greedy algo for Knapsack (very natural: pick according to the ratio value-to-weight) can be arbitrarily bad, as 35.1% of you answered: ω(1)-approx. (Like, Ω(n)-bad 🤯).
Bummer. 😯
Bummer! 😞
But...! 🤔
9/
... there is a very, very simple fix to get a 2-approx! Just use the same Greedy algo. Just do it.
Then, at the end, return the best of TWO solutions: (1) what the Greedy algo returned, and (2) one item, "k+1,", the first Greedy refused to pick.
That's all. That's it.
10/
There is a lot of work on greedy algos, including understanding under which set of conditions they always lead to optimal solutions: matroid structures, etc.
Definitely worth looking into, if you're interested!
11/
en.wikipedia.org/wiki/Greedy_al…
Also, many mentions (and an entire chapter) in Shmoys–Williamson's (excellent) book on approximation #algorithms: designofapproxalgs.com
(the website provides a free PDF version!)
12/
To conclude, I'll leave you with this open-ended Q, and the v. good answers *you* have provided to it: EM, Lloyd-max, Stable Marriage, Huffman coding, Kosaraju’s algo for strongly connected components, policy iteration, & more!
See you next week!
13/end
Share this Scrolly Tale with your friends.
A Scrolly Tale is a new way to read Twitter threads with a more visually immersive experience.
Discover more beautiful Scrolly Tales like this.