Clustering Permutations: New Techniques with Streaming Applications

on YouTube ↗26m

" summary

Presents a concrete algorithm that gives a 1.99-approximation for the Ulam 1‑median (improving over the prior 2−ε with ε ≈ 2^−40), extends to k‑median and outliers, and implements in insertion‑only streams. Key tools: either an input permutation is already near the optimum, or there is a large cluster around some input, or one can reconstruct from five permutations to produce a good median; using k^2 polylog n sampling yields a small‑space streaming coreset and polytime k‑median selection.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 0:14Problem under Consideration
3. 1:22Finding a Median String
4. 3:43Approximate Median
5. 5:29Permutations - a special case?
6. 8:53Ulam metric - a special case? Not Really
7. 9:23Why to study Ulam Median?
8. 10:40Rank Aggregation / (Ulam) Median
9. 14:52What do we know?
10. 18:08Finding a Median: A New Approach
11. 21:09Finding a Median: Final Algorithm
12. 22:32k-median: An Extension
13. 24:28What about Streaming?
14. 25:07What about Streaming k-median?
15. 25:31Open Problems