Inapproximability of Maximum Diameter Clustering for Few Clusters

In the Max-k-Diameter problem, we are given a set of points in a metric space, and the goal is to partition the input points into k parts such that the maximum pairwise distance between points in the same part of the partition is minimized.

The approximability of the Max-k-Diameter problem was studied in the eighties, culminating in the work of Feder and Greene [STOC'88], wherein they showed it is NP-hard to approximate within a factor better than 2 in the ℓ 1 and ℓ ∞ metrics, and NP-hard to approximate within a factor better than 1.969 in the Euclidean metric. This complements the celebrated 2 factor polynomial time approximation algorithm for the problem in general metrics (Gonzalez [TCS'85]; Hochbaum and Shmoys [JACM'86]).

Over the last couple of decades, there has been increased interest from the algorithmic community to study the approximability of various clustering objectives when the number of clusters is fixed. In this setting, the framework of coresets has yielded PTAS for most popular clustering objectives, including k-means, k-median, k-center, k-minsum, and so on.

In this paper, rather surprisingly, we prove that even when k = 3, the Max-k-Diameter problem is NP-hard to approximate within a factor of 1.5 in the ℓ 1 -metric (and Hamming metric) and NP-hard to approximate within a factor of 1.304 in the Euclidean metric.

Our main conceptual contribution is the introduction of a novel framework called cloud systems which embed hypergraphs into ℓ p -metric spaces such that the chromatic number of the hypergraph is related to the quality of the Max-k-Diameter clustering of the embedded pointset. Our main technical contributions are the constructions of nontrivial cloud systems in the Euclidean and ℓ 1 -metrics using extremal geometric structures.