The \(l\)-diversity problem: tractability and approximability

DOI10.1016/j.tcs.2012.05.024zbMath1358.68128OpenAlexW1974150157WikidataQ57518445 ScholiaQ57518445MaRDI QIDQ392037

Giancarlo Mauri, Italo Zoppis, Riccardo Dondi

Publication date: 13 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.05.024

zbMATH Keywords

parameterized complexity\(k\)-anonymity\(l\)-diversityapproximation complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

The effect of homogeneity on the computational complexity of combinatorial data anonymization

Uses Software

• PrivateLR

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]
• Fixed-parameter tractability of anonymizing data by suppressing entries
• Some APX-completeness results for cubic graphs
• Algorithmic construction of sets for k -restrictions
• Parameterized Complexity of k-Anonymity: Hardness and Tractability
• Integer Programming with a Fixed Number of Variables
• Pattern-Guided Data Anonymization and Clustering
• On the Complexity of the l-diversity Problem
• The Effect of Homogeneity on the Complexity of k-Anonymity
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Clustering with Diversity
• Resolving the Complexity of Some Data Privacy Problems
• Minkowski's Convex Body Theorem and Integer Programming
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
• Database Theory - ICDT 2005
• Differential Privacy

This page was built for publication: The \(l\)-diversity problem: tractability and approximability