CCE Faculty Articles

Approximation bounds for minimum information loss microaggregation

Document Type

Article

Publication Title

IEEE Transactions on Knowledge and Data Engineering

ISSN

1041-4347

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

Volume

21

Issue

11

First Page

1643

Last Page

1647

Link to Full Text

Find in your library

Share

COinS