Hardness of k-anonymous microaggregation

Florian Thaeter*, Rüdiger Reischuk

*Corresponding author for this work


k-anonymous microaggregation of data in Rd with d≥2 is shown to be NP-hard for all k≥4, extending a previous result for the case k=3 only. The proof uses similarities between microaggregation and the k-means problem. A reduction of Planar 3-SAT to the k-means clustering problem is adapted to 4-anonymous clustering. Then this construction is extended to arbitrary k≥4.

Original languageEnglish
JournalDiscrete Applied Mathematics
Publication statusPublished - 27.10.2020

DFG Research Classification Scheme

  • 409-01 Theoretical Computer Science


Dive into the research topics of 'Hardness of k-anonymous microaggregation'. Together they form a unique fingerprint.

Cite this