Anonymizing binary and small tables is hard to approximate
From MaRDI portal
Publication:543515
DOI10.1007/s10878-009-9277-yzbMath1242.90187OpenAlexW1995665378MaRDI QIDQ543515
Paola Bonizzoni, Riccardo Dondi, Gianluca Della Vedova
Publication date: 17 June 2011
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-009-9277-y
Related Items
Parameterized complexity of \(k\)-anonymity: hardness and tractability ⋮ The \(l\)-diversity problem: tractability and approximability ⋮ The effect of homogeneity on the computational complexity of combinatorial data anonymization ⋮ On the inapproximability of maximum intersection problems ⋮ \(k\)-attribute-anonymity is hard even for \(k=2\) ⋮ Pattern-guided \(k\)-anonymity ⋮ The Effect of Homogeneity on the Complexity of k-Anonymity ⋮ A refined complexity analysis of degree anonymization in graphs
Cites Work
- Unnamed Item
- Approximation algorithms for Hamming clustering problems
- Some APX-completeness results for cubic graphs
- Finding similar regions in many sequences
- Achieving anonymity via clustering
- k-Anonymization with Minimal Loss of Information
- k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
- Database Theory - ICDT 2005
- Fixed-Parameter Tractability of Anonymizing Data by Suppressing Entries
