CCE Faculty Articles
Approximation bounds for minimum information loss microaggregation
Document Type
Article
Date
11-1-2009
Publication Title
IEEE Transactions on Knowledge and Data Engineering
ISSN or ISBN
1041-4347
Volume
21
Issue
11
First Page
1643
Last Page
1647
Description
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 {\rm O}(k^3) guarantee for this objective function and an {\rm O}(k^2) 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 {\rm O}(k^2) for the squared distance measure and {\rm O}(k) for the distance measure.
DOI
10.1109/TKDE.2009.78
NSUWorks Citation
Laszlo, Michael J. and Mukherjee, Sumitra, "Approximation bounds for minimum information loss microaggregation" (2009). CCE Faculty Articles. 3.
https://nsuworks.nova.edu/gscis_facarticles/3