Parameterized complexity of \(k\)-anonymity: hardness and tractability

DOI10.1007/s10878-011-9428-9zbMath1300.90033OpenAlexW3098107898MaRDI QIDQ358665

Yuri Pirola, Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi

Publication date: 9 August 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-011-9428-9

zbMATH Keywords

approximation algorithmshardnessanonymityfixed-parameter complexity

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (4)

\(k\)-attribute-anonymity is hard even for \(k=2\) ⋮ Pattern-guided \(k\)-anonymity ⋮ Error Detection and Correction of Gene Trees ⋮ A refined complexity analysis of degree anonymization in graphs

Uses Software

• UCI-ml

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Anonymizing binary and small tables is hard to approximate
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Fixed-parameter tractability of anonymizing data by suppressing entries
• Some APX-completeness results for cubic graphs
• Achieving anonymity via clustering
• On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem
• Resolving the Complexity of Some Data Privacy Problems
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
• Database Theory - ICDT 2005

This page was built for publication: Parameterized complexity of \(k\)-anonymity: hardness and tractability