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

2 Zitate (Scopus)

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

UN SDGs

Dieser Output leistet einen Beitrag zu folgendem(n) Ziel(en) für nachhaltige Entwicklung

SDG 9 – Industrie, Innovation und Infrastruktur

DFG-Fachsystematik

4.43-01 Theoretische Informatik

Dokumente

10.1016/j.dam.2020.10.005

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

publisher = "Elsevier B.V.",

}

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 - https://www.scopus.com/pages/publications/85094557514

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

UN SDGs

DFG-Fachsystematik

Dokumente

Weitere Links

Fingerprint

Zitieren