|
Solving the Disclosure Auditing Problem for Secondary Cell Suppression by Means of Linear Programming
Ton de Waal(a),(b),(*), Wieger Coutinho(c)
Transactions on Data Privacy 13:2 (2020) 67 - 90
Abstract, PDF
(a) Statistics Netherlands, PO Box 24500, 2490 HA, The Hague, The Netherlands.
(b) Tilburg University, PO Box 90153, 5000 LE, Tilburg, The Netherlands.
(c) Dunea, Plein van de Verenigde Naties 11-15, 2719 EG, Zoetermeer, The Netherlands.
e-mail:t.dewaal @cbs.nl;
|
|
Abstract
National Statistical Institutes (NSIs) have the obligation to protect the privacy of individual persons or enterprises against disclosure of potentially sensitive information. For this reason, NSIs protect tabular data against disclosure of sensitive information before they are released. For tabular magnitude data, the starting point of this protection process usually is a sensitivity measure for individual cells. Such a sensitivity measure defines when a cell value is considered safe for publication or not. An often used method to protect a table with unsafe cells against disclosure of sensitive information is cell suppression. [5] argues that the standard criterion for deciding whether a table after suppression is safe or not is somewhat inconsistent and proposes a new criterion. [5] also gives a mixed-integer programming problem formulation for applying this new criterion. The problem with that formulation is that it is quite large and very hard to solve for even moderately sized tables. To be more precise, that mixed-integer programming problem formulation suggests that the auditing problem based on the criterion of [5] is NP-hard. The general assumption among operations research experts is that the computing time for NP-hard problems is non-polynomial in their input parameters. In the current paper, we propose solving a number of smaller and computationally much easier linear programming problems instead of solving one large mixed-integer programming problem. Solving linear programming problems can be done in time polynomial in their input parameters.
|
