their algorithm is exponential in the number of columns $m$ (but, polynomial in the number of rows $n$).

We make the following observations regarding the previously known results. Firstly, the known NP-hardness reductions produce tables in which the number of columns is arbitrarily large. This is not satisfactory as the number of columns in practical settings is not large. Secondly, the algorithm of Park and Shim [@SIGMOD] is a polynomial time $O(\log k)$-approximation algorithm when the number of columns $m$ is small ($m=O(\log n)$). These observations raise a natural question: Does the $k$-anonymization problem remain NP-Complete even when the number of columns $m$ is small ($\log n$ or a constant)? We show that the $k$-anonymization problem remains NP-hard, even when the number columns $m$ is fixed to be a constant ($m=3$). In fact, we also show that the above restricted version is MAXSNP-hard, thus ruling out polynomial time approximation schemes. We also derive that the problem cannot be approximated within a factor of $\frac{6238}{6237}$. Even though our inapproximability bound is mild, it is the first explicit inapproximability bound proved for the $k$-anonymization problem. All our hardness results hold even when the privacy parameter $k$ is a constant ($k=7$).

As we 