Lower-bounding procedures for the 2-dimensional cell suppression problem

To protect confidential data from disclosure, statistical offices use a technique called cell suppression which consists of suppressing data from the statistical tables they publish. As some row and column subtotals are published, omitting just the confidential values does not guarantee in every case that they cannot be disclosed or estimated within a narrow range. Therefore to protect confidential data it is often necessary to make complementary suppressions, that is, to suppress also values that are not confidential. Assigning a cost to every complementary suppression, the cell suppression problem is that of finding a set of complementary suppressions with minimum total cost. In this paper new necessary protection conditions are presented. Combining these new conditions with the ones known from the literature new lower-bounding methods for the cell suppression problem are developed. Dominance theoretical results are proven and computational experience is reported for randomly generated tables. (C) 2000 Elsevier Science B.V. All rights reserved.