Completed
Hardness of Approximation
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Inapproximability of Clustering in Lp Metrics
Automatically move to the next video in the Classroom when playback concludes
- 1 Introduction
- 2 Structure of computational problems
- 3 Clustering
- 4 Continuous Clustering
- 5 Clustering is a Hard Problem
- 6 Approximation Algorithms
- 7 Hardness of Approximation
- 8 Results
- 9 Proof
- 10 Vertex Edge Game
- 11 Randomness
- 12 Graph embedding
- 13 Key takeaways
- 14 Johnson Coverage Hypothesis
- 15 In Approximability
- 16 Conclusion
- 17 Questions