noted, the previous constructions ensured that the alphabet size is a fixed constant; but, in our constructions, the alphabet size is not a fixed constant, but it is arbitrarily large. However, this is not a serious issue; in most settings, tables have large number of unique entries (for example, a zipcode column takes a large number of distinct values). In the wake of previous results and our results mentioned above, a natural question is whether the problem is NP-hard when both the number of columns $m$ and the alphabet size $|\Sigma|$ are small. We show that the problem can be solved optimally in polynomial time when both $m$ and $|\Sigma|$ are fixed constants.

Below, we summarize the new results proved in this paper.

-   The $k$-anonymization problem is NP-hard even when the number of columns $m$ and the privacy parameter $k$ are constants ($m=3$, $k=7$). We show that the restricted version is MAXSNP-hard and cannot be approximated within a factor of $\frac{6238}{6237}$.

-   When both the number of columns and the alphabet size are fixed constants, the problem can be solved optimally in polynomial time. The result is true, even when the privacy parameter $k$ is arbitrarily large.

The known 