We study the following algorithmic problem: given n points within a finite d-dimensional box, what is the smallest number of extra points that need to be added to ensure that every d-dimensional unit box is either empty, or contains at least k points. We motivate the problem through an application to data privacy, namely k-anonymity. We show that minimizing the number of extra points to be added is strongly NP-complete, but admits a Polynomial Time Approximation Scheme (PTAS). In some sense, this is the best we can hope for, since a Fully Polynomial Time Approximation Scheme (FPTAS) is not possible, unless P=NP.
['Victor Josué Álvarez', 'Erin W. Chambers', 'László Kozma']
Privacy by Fake Data: A Geometric Approach