k-attribute-anonymity is hard even for k=2

DOI10.1016/J.IPL.2014.10.011zbMATH Open1302.68128OpenAlexW2029584013MaRDI QIDQ477690FDOQ477690

Authors: Allan Scott, Venkatesh Srinivasan, Ulrike Stege 

Publication date: 9 December 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2014.10.011

Recommendations

• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• The k-Anonymity Problem Is Hard
• Database Theory - ICDT 2005
• Anonymizing binary and small tables is hard to approximate
• Parameterized complexity of \(k\)-anonymity: hardness and tractability

zbMATH Keywords

computational complexityNP-hardnessfixed parameter tractabilitydata anonymizationdatabase privacy

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15) Authentication, digital signatures and secret sharing (94A62)

Cites Work

• Title not available (Why is that?)
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• Resolving the Complexity of Some Data Privacy Problems
• Database Theory - ICDT 2005
• Anonymizing binary and small tables is hard to approximate
• Fixed-parameter tractability of anonymizing data by suppressing entries
• The effect of homogeneity on the computational complexity of combinatorial data anonymization
• Pattern-guided \(k\)-anonymity

Cited In (1)

• Anonymizing binary and small tables is hard to approximate

This page was built for publication: \(k\)-attribute-anonymity is hard even for \(k=2\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477690)