On the Complexity of the $k$-Anonymization Problem

Details On the Complexity of the $k$-Anonymization Problem On the Complexity of the $k$-Anonymization Problem

2010-04-27

arxiv.org/abs/1004.4729v1

Computer Science

Computational Complexity

9 pages, 2 figures

Scientific paper

We study the problem of anonymizing tables containing personal information before releasing them for public use. One of the formulations considered in this context is the $k$-anonymization problem: given a table, suppress a minimum number of cells so that in the transformed table, each row is identical to atleast $k-1$ other rows. The problem is known to be NP-hard and MAXSNP-hard; but in the known reductions, the number of columns in the constructed tables is arbitrarily large. However, in practical settings the number of columns is much smaller. So, we study the complexity of the practical setting in which the number of columns $m$ is small. We show that the problem is NP-hard, even when the number of columns $m$ is a constant ($m=3$). We also prove MAXSNP-hardness for this restricted version and derive that the problem cannot be approximated within a factor of (6238/6237). Our reduction uses alphabets $\Sigma$ of arbitrarily large size. A natural question is whether the problem remains NP-hard when both $m$ and $|\Sigma|$ are small. We prove that the $k$-anonymization problem is in $P$ when both $m$ and $|\Sigma|$ are constants.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of the $k$-Anonymization 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 On the Complexity of the $k$-Anonymization Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of the $k$-Anonymization Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-236923