Privacy by Fake Data: A Geometric Approach
Víctor Álvarez, Erin Wolf Chambers, László Kozma · 2013
Abstract. 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 everyd-dimensional unit box is either empty, or contains at least k points. We motivate the problem through a possible application to data privacy. 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. 1