Computer Science – Data Structures and Algorithms
Scientific paper
2009-10-16
Computer Science
Data Structures and Algorithms
22 pages, 2 figures
Scientific paper
The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization that has been recently proposed is the $k$-anonymity. This approach requires that the rows of a table are partitioned in clusters of size at least $k$ and that all the rows in a cluster become the same tuple, after the suppression of some entries. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is known to be APX-hard even when the records values are over a binary alphabet and $k=3$, and when the records have length at most 8 and $k=4$ . In this paper we study how the complexity of the problem is influenced by different parameters. In this paper we follow this direction of research, first showing that the problem is W[1]-hard when parameterized by the size of the solution (and the value $k$). Then we exhibit a fixed parameter algorithm, when the problem is parameterized by the size of the alphabet and the number of columns. Finally, we investigate the computational (and approximation) complexity of the $k$-anonymity problem, when restricting the instance to records having length bounded by 3 and $k=3$. We show that such a restriction is APX-hard.
Beretta Stefano
Bonizzoni Paola
Dondi Riccardo
Pirola Yuri
Vedova Gianluca Della
No associations
LandOfFree
Parameterized Complexity of the k-anonymity Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Parameterized Complexity of the k-anonymity Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterized Complexity of the k-anonymity Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-124192