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.