Inapproximability of Maximum Diameter Clustering for Few Clusters
Henry Fleischmann, Kyrylo Karlov, C. S. Karthik, Ashwin Padaki, Stepan Zharkov · Society for Industrial and Applied Mathematics eBooks · 2025
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.