Skip to main content
Article
Approximation bounds for minimum information loss microaggregation
IEEE Transactions on Knowledge and Data Engineering
  • Michael J Laszlo, Nova Southeastern University
  • Sumitra Mukherjee, Nova Southeastern University
Document Type
Article
Publication Date
11-1-2009
Abstract

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
Disciplines
Citation Information
Michael J Laszlo and Sumitra Mukherjee. "Approximation bounds for minimum information loss microaggregation" IEEE Transactions on Knowledge and Data Engineering Vol. 21 Iss. 11 (2009) p. 1643 - 1647 ISSN: 1041-4347
Available at: http://works.bepress.com/michael-laszlo/8/