Parameterized complexity of k-anonymity: hardness and tractability

DOI10.1007/S10878-011-9428-9MaRDI QIDQ358665zbMATH OpenOpenAlexFDO

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

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 algorithmshardnessfixed-parameter complexityanonymity

Mathematics Subject Classification ID

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

Recommendations

• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• Fixed-parameter tractability of anonymizing data by suppressing entries
• Fixed-Parameter Tractability of Anonymizing Data by Suppressing Entries
• The k-Anonymity Problem Is Hard
• Anonymizing binary and small tables is hard to approximate

Cites work

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

Cited in

(18)

• The l-diversity problem: tractability and approximability
• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• Hardness of \(k\)-anonymous microaggregation
• The effect of homogeneity on the computational complexity of combinatorial data anonymization
• Error detection and correction of gene trees
• Privacy in elections: \(k\)-anonymizing preference orders
• Fixed-Parameter Tractability of Anonymizing Data by Suppressing Entries
• Pattern-guided \(k\)-anonymity
• The k-Anonymity Problem Is Hard
• On the complexity of the \(l\)-diversity problem
• The effect of homogeneity on the complexity of \(k\)-anonymity
• A fixed-parameter approach for privacy-protection with global recoding
• \(k\)-attribute-anonymity is hard even for \(k=2\)
• Database Theory - ICDT 2005
• A refined complexity analysis of degree anonymization in graphs
• Anonymizing binary and small tables is hard to approximate
• Fixed-parameter tractability of anonymizing data by suppressing entries
• Pattern-guided \(k\)-anonymity

Describes a project that uses

Uses Software

• UCI

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

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