of $k$-anonymity, which aims to preserve privacy either by suppressing or generalizing some of the sensitive data values.

In this paper, we consider the basic $k$-anonymity problem with only suppression allowed. Suppose we have a table with $n$ rows and $m$ columns. In order to achieve anonymity, one is allowed to suppress the entries of the table so that in the modified table, every row is identical to at least $k-1$ other rows. The goal is to minimize the number of cells suppressed. This is called the [*$k$-anonymization*]{} problem. The motivation for the problem formulation are twofold: (i) any join attack would return groups of at least $k$ rows, thus preserving privacy with a parameter of $k$; (ii) lesser the number of entries suppressed, better is the value of the modified table for data mining.

[**Example:** ]{}We now illustrate the problem definition with an example. An example input table and its anonymized output, for $k=2$, are shown in Figure \[fig:example\]. The number of rows is $n=4$ and number of columns is $m=3$. The suppressed cells are shown by “$*$”. We see that in the anonymized output table, the first and the third rows are identical, and the second and the 