Approximation Bounds for Minimum Information Loss Microaggregation

The NP-hard microaggregation problem seeks a partition of data points into groups of minimum specified size k, so as to minimize the sum of the squared euclidean distances of every point to its group´s centroid. One recent heuristic provides an O(k³) guarantee for this objective function and an O(k²) guarantee for a version of the problem that seeks to minimize the sum of the distances of the points to its group´s centroid. This paper establishes approximation bounds for another microaggregation heuristic, providing better approximation guarantees of O(k²) for the squared distance measure and O(k) for the distance measure.