Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/TKDE.2009.78 | Knowledge and Data Engineering, IEEE Transactions |
Keywords | Field | DocType |
computational complexity,data privacy,security of data,NP-hard microaggregation problem,approximation bounds,euclidean distances,group centroid,minimum information loss microaggregation,squared distance measure,Data security,approximation algorithms,disclosure control,graph partitioning,information loss.,k-anonymity,microaggregation,microdata protection | Graph theory,Discrete mathematics,Data mining,Approximation algorithm,Heuristic,Combinatorics,Square (algebra),Graph partition,Partition (number theory),Mathematics,Centroid,Computational complexity theory | Journal |
Volume | Issue | ISSN |
21 | 11 | 1041-4347 |
Citations | PageRank | References |
7 | 0.51 | 18 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Laszlo | 1 | 214 | 10.76 |
| Sumitra Mukherjee | 2 | 311 | 31.75 |