Share this page!

Enter URL or ID to Unroll

You can paste full URL like: https://x.com/threadreaderapp/status/1644127596119195649
or just the ID like: 1644127596119195649

How to get URL link on X (Twitter) App

  1. On the Twitter thread, click on or icon on the bottom
  2. Click again on or Share Via icon
  3. Click on Copy Link to Tweet
  4. Paste it above and click "Unroll Thread"!
  5. More info at Twitter Help
Clément Canonne Profile picture
@ccanonne_
Aug 22, 2021 • 13 tweets • 6 min read • Read on X
Scrolly
📊 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

• • •

Missing some Tweet in this thread? You can try to force a refresh
　

Keep Current with Clément Canonne

Clément Canonne Profile picture

Stay in touch and get notified when new unrolls are available from this author!

Read all threads

This Thread may be Removed Anytime!

PDF

Twitter may remove this content at anytime! Save it as PDF for later use!

Try unrolling a thread yourself!

how to unroll video
  1. Follow @ThreadReaderApp to mention us!

  2. From a Twitter thread mention us with a keyword "unroll"
@threadreaderapp unroll

Practice here first or read more on our help page!

More from @ccanonne_

Clément Canonne Profile picture
Aug 8, 2022
🧩 Answers and discussions for last week's quiz on (some) inequalities, and hopefully a teaser for many others you may find useful.

Today's menu: union 🧅 bound (and a partial converse), Bernoulli's inequality (but which Bernoulli?), Abel's, and Chebyshev's (not that one!).

1/
Let's start with a PSA: print this. Hang it on the wall near your desk. Make it a t-shirt and wear it to work. lkozma.net/inequalities_c…

It is the single most useful list of inequalities I have ever encountered, and it's a goddamn treasure. (Even if you only ever use a subset!)
2/
Alright, here we go: the union🧅 bound! It's simple, it's effective, and it works. As 76% of you correctly answered, it comes w/ no strings attached: no independence assumptions, no nothing!

Pr[⋃] ≤ ∑ Pr

(Also generalizes to countable sums/unions).

3/
Read 21 tweets
Clément Canonne Profile picture
Nov 27, 2021
Oh, this is a fun one!

(From "Experimentation in Mathematics: Computational Paths to Discovery," Borwein, Bailey, and Girgensohn, 2004)
Answered in the affirmative in 2005 by Ravi B. Boppana (and made available in 2020 on arxiv.org/abs/2007.11017.)

Simpler proofs? Better bounds? Variations? Also, that book contains a lot of cool stuff.
The proof is really nice. You can divide the series in two sums: those over the "tame" numbers (for which sin n is significantly far from 1, roughly sin n < 1-1/√n), and the "wild" ones (damn, sin n ≈ 1).

The sum over tame numbers then easily converges, as ∑(1-1/√n)ⁿ does..
Read 7 tweets
Clément Canonne Profile picture
Nov 25, 2021
📊 Friday here, Thursday there, time for a quiz! The wait is over: now, we weigh. ⚖️

You've been given n indistinguishable (to the eye) potatoes. It is very important to you that they all are identical, and in particular all have the same weight.

Do they though?

1/
Your urgent and all-important task is thus to check whether all n 🥔 have the same exact weight, or if you've been cheated by the potatomonger: their weights, on average, significant depart from identical (average 🥔 weight).

Classic.

Now, how does one do that?

2/ Image
Absent any fancy measuring device, your first approach is quite natural: throw all 🥔s with equal strength, see which one goes the farthest (and repeat). It's very tiring, but it lets you sample a 🥔 based on its weight.

By seeing where the chips have fallen, if you will.

3/
Read 13 tweets
Clément Canonne Profile picture
Aug 23, 2021
My first foray into shuffle #privacy, spearheaded by my impressive winter research intern Hongyi Lyu (maths undergrad @UniMelb), who managed to learn about DP+shuffle DP+distribution testing, all this in ~6 weeks!

Comments welcome! 📝 arxiv.org/abs/2108.08987
1/4
This was part of the "Winter/Summer Research Internship" program at @Eng_IT_Sydney @Sydney_Uni:
sydney.edu.au/engineering/st…

Our (short) paper builds on|simplifies an algo of Balcer, Cheu, @mgtjoseph, & Mao. One key component of our analysis? This fact!


2/4
We also use the recent amplification theorem of @vitalyFM, McMillan, and @_kunal_talwar_ (local privacy to shuffle privacy) to provide an alternative algo:

3/4
Read 5 tweets
Clément Canonne Profile picture
Aug 21, 2021
Ninth #AcademicSpotlight: Donlapark Ponnoprat (@BomNaKub), Lecturer at @cmuofficial_tw

Paper: Universal Consistency of Wasserstein k-NN classifiers 📝
arxiv.org/abs/2009.04651

Pitch: understanding universal consistency of the k-NN classifier under Wasserstein distances!

1/4
In more detail: A binary classifier g(Dₙ) trained on dataset Dₙ is universally consistent (UC) if the error proba Pₓ,ᵧ(g(Dₙ)(X)≠Y|Dₙ) converges to the Bayes risk as n→∞, regardless of the joint distribution of X and Y. This paper studies the universal consistency...

2/4
... of the k-NN classifier on spaces of proba measures under p-Wasserstein distance. From studying geometric properties of Wasserstein spaces, we show that the k-NN classifier is (1) UC for any p≥1 on the space of measures finitely supported in ℚᵈ with rational masses...
3/4
Read 4 tweets
Clément Canonne Profile picture
Mar 30, 2021
Here is one:
If X has the same distribution as X', Y as Y', and Z as Z', do we have 𝔼[X+Y+Z]=𝔼[X'+Y'+Z']?
Note that this is true for only two r.v.'s: if X~X' and Y~Y'
𝔼[X+Y]=𝔼[X'+Y']
whenever 𝔼[X+Y] is defined (regardless of whether 𝔼[X] and 𝔼[Y] are defined). (cf. below from G. Simons (1977)).
Turns out, this fails for 3 r.v.'s (same paper by Simons, and Counterexample 6.1 in Stoyanov's book).

Sometimes 𝔼[X+Y+Z], 𝔼[X'+Y'+Z'] both exist, yet 𝔼[X+Y+Z]≠𝔼[X'+Y'+Z'].

(Again, for 2 r.v.'s the result holds: if 𝔼[X+Y], 𝔼[X'+Y'] both exist, then 𝔼[X+Y]=𝔼[X'+Y'].)
Read 5 tweets

Did Thread Reader help you today?

Support us! We are indie developers!

This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3/month or $30/year) and get exclusive features!

Become Premium

Don't want to be a Premium member but still want to support us?

Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal

Or Donate anonymously using crypto!

Ethereum

0xfe58350B80634f60Fa6Dc149a72b4DFbc17D341E copy

Bitcoin

3ATGMxNzCUFzxpMCHL5sWSt4DVtS8UqXpi copy

Thank you for your support!

Follow Us!

Send Email!

:(