We study the problem of protecting sensitive data in a statistical two-dimensional table, when the non-sensitive table entries are made public along with the row and column totals. In particular, we address the NP-hard problem known in the literature as the (secondary) cell suppression problem. We introduce a new integer linear programming model and describe several new families of additional inequalities used to strengthen the linear relaxation of the model. Exact and heuristic separation procedures are also proposed and embedded within a branch-and-cut algorithm for the exact solution of the problem. The algorithm makes use of an efficient heuristic procedure to find near-optimal solutions. We report the exact solution of instances involving up to 250,000 cells and 10,000 sensitive cells, i.e., more than 3 orders of magnitude larger than those solved by previous techniques from the literature. © Springer-Verlag 1999.

Models and algorithms for the 2-dimensional cell suppression problem in statistical disclosure control

Fischetti M.;
1999

Abstract

We study the problem of protecting sensitive data in a statistical two-dimensional table, when the non-sensitive table entries are made public along with the row and column totals. In particular, we address the NP-hard problem known in the literature as the (secondary) cell suppression problem. We introduce a new integer linear programming model and describe several new families of additional inequalities used to strengthen the linear relaxation of the model. Exact and heuristic separation procedures are also proposed and embedded within a branch-and-cut algorithm for the exact solution of the problem. The algorithm makes use of an efficient heuristic procedure to find near-optimal solutions. We report the exact solution of instances involving up to 250,000 cells and 10,000 sensitive cells, i.e., more than 3 orders of magnitude larger than those solved by previous techniques from the literature. © Springer-Verlag 1999.
1999
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3389515
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 34
  • ???jsp.display-item.citation.isi??? 36
  • OpenAlex ND
social impact