Abstract
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 language | English |
---|---|
Journal | Discrete Applied Mathematics |
ISSN | 0166-218X |
DOIs | |
Publication status | Published - 27.10.2020 |
DFG Research Classification Scheme
- 4.43-01 Theoretical Computer Science