Inapproximability of Clustering in Lp Metrics

Explore the complexities of clustering algorithms in Lp metrics through this 21-minute IEEE conference talk. Delve into the structure of computational problems, focusing on continuous clustering and its inherent difficulties. Examine approximation algorithms and the hardness of approximation in this context. Learn about key concepts such as the Vertex Edge Game, randomness, and graph embedding. Understand the significance of the Johnson Coverage Hypothesis in inapproximability. Gain valuable insights into the challenges of clustering problems and their implications in computational complexity theory.

Introduction
Structure of computational problems
Clustering
Continuous Clustering
Clustering is a Hard Problem
Approximation Algorithms
Hardness of Approximation
Results
Proof
Vertex Edge Game
Randomness
Graph embedding
Key takeaways
Johnson Coverage Hypothesis
In Approximability
Conclusion
Questions