Inapproximability of Clustering in Lp Metrics

Inapproximability of Clustering in Lp Metrics

IEEE FOCS: Foundations of Computer Science via YouTube Direct link

Hardness of Approximation

7 of 17

7 of 17

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. 1 Introduction
  2. 2 Structure of computational problems
  3. 3 Clustering
  4. 4 Continuous Clustering
  5. 5 Clustering is a Hard Problem
  6. 6 Approximation Algorithms
  7. 7 Hardness of Approximation
  8. 8 Results
  9. 9 Proof
  10. 10 Vertex Edge Game
  11. 11 Randomness
  12. 12 Graph embedding
  13. 13 Key takeaways
  14. 14 Johnson Coverage Hypothesis
  15. 15 In Approximability
  16. 16 Conclusion
  17. 17 Questions

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.