Solving the disclosure auditing problem for secondary cell suppression by means of linear programming

Ton de Waal*, Wieger Coutinho

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

124 Downloads (Pure)


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
Original languageEnglish
Pages (from-to)67-90
JournalTransactions on Data Privacy
Issue number2
Publication statusPublished - 2020


Dive into the research topics of 'Solving the disclosure auditing problem for secondary cell suppression by means of linear programming'. Together they form a unique fingerprint.

Cite this