fourth rows are identical. Thus the table on the right is $2$-anonymized. The cost of this anonymization is $4$, since $4$ cells are suppressed. This is an optimal solution.

[ccccc]{}

   $x$   $a$   $b$
  ----- ----- -----
   $z$   $c$   $d$
   $y$   $a$   $b$
   $z$   $c$   $e$

& & & &

   $*$   $a$   $b$
  ----- ----- -----
   $z$   $c$   $*$
   $*$   $a$   $b$
   $z$   $c$   $*$

\
&&&&\
Original table & & & & $2$-Anonymized table

[**Known and New Results:** ]{}

Meyerson and Williams [@MW] proved the NP-hardness of the $k$-anonymization problem. Aggarwal et al. [@ICDT] improved the result by showing that the problem remains NP-hard even when the alphabet $\Sigma$ from which the symbols of the table are drawn is fixed to be ternary. Bonizzoni et al [@APX-hard] proved MAXSNP-hardness (and NP-hardness) even when the alphabet is binary. The value of the privacy parameter $k$ is a fixed constant in all the above results ($k=3$). On the algorithmic front, Meyerson and Williams gave a $O(k\log k)$-approximation algorithm. This was improved by Aggarwal et al. [@ICDT], who devised a $O(k)$-approximation algorithm. Park and Shim [@SIGMOD] presented an approximation algorithm with a ratio of $O(\log{k})$; however, we observe that the running time of 