Approximation Algorithms for Aversion k-Clustering via Local k-Median

摘要

In the aversion k-clustering problem, given a metric space, we want to cluster the points into k clusters. The cost incurred by each point is the distance to the furthest point in its cluster, and the cost of the clustering is the sum of all these per-poi