A shortest-paths heuristic for statistical data protection in positive tables

National statistical agencies (NSAs) routinely release large amounts of tabular information. Prior to dissemination, tabular data need to be processed to avoid disclosure of individual confidential information. Cell suppression is one of the most widely used techniques by NSAs. Optimal procedures for cell suppression are computationally expensive with large real–world data sets, so heuristic procedures are used. Most heuristics for positive tables (i.e., cell values are nonnegative) rely on the solution of minimum–cost network–flows subproblems. A very efficient heuristic based on shortest paths already exists, but it is only appropriate for general tables (i.e., cell values can be either positive or negative), whereas in practice most tables are positive. We present a method that sensibly combines and improves previous approaches, overcoming some of their drawbacks: it is designed for positive tables and requires only the solution of shortest–path subproblems—therefore being much more efficient than other network–flows heuristics. We report extensive computational experience in the solution of randomly generated and real–world instances, comparing the heuristic with alternative procedures. The results show that the method, currently included in a software package for statistical data protection, fits NSA needs: it is extremely efficient and provides good solutions.