Hardness of k-anonymous microaggregation

Florian Thaeter; Rüdiger Reischuk

doi:10.1016/j.dam.2020.10.005

Hardness of k-anonymous microaggregation

Florian Thaeter^*, Rüdiger Reischuk

^*Korrespondierende/r Autor/-in für diese Arbeit

Institut für Theoretische Informatik

Abstract

k-anonymous microaggregation of data in R^d 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.

Originalsprache	Englisch
Zeitschrift	Discrete Applied Mathematics
ISSN	0166-218X
DOIs	https://doi.org/10.1016/j.dam.2020.10.005
Publikationsstatus	Veröffentlicht - 27.10.2020

Zugriff auf Dokument

10.1016/j.dam.2020.10.005

Andere Dateien und Links

Link to publication in Scopus

Zitieren

@article{0a30d19e82c146d7906016146029b685,

title = "Hardness of k-anonymous microaggregation",

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.",

author = "Florian Thaeter and R{\"u}diger Reischuk",

year = "2020",

month = oct,

day = "27",

doi = "10.1016/j.dam.2020.10.005",

language = "English",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

}

TY - JOUR

T1 - Hardness of k-anonymous microaggregation

AU - Thaeter, Florian

AU - Reischuk, Rüdiger

PY - 2020/10/27

Y1 - 2020/10/27

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85094557514&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2020.10.005

DO - 10.1016/j.dam.2020.10.005

M3 - Journal articles

AN - SCOPUS:85094557514

SN - 0166-218X

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Hardness of k-anonymous microaggregation

Abstract

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Zitieren