fixed as $k=7$.

Moreover, [[Chlebík]{}]{} and [[Chlebíkov[á]{}]{}]{} [@Chlebik] showed that the vertex cover problem on 3-regular graphs cannot be approximated within a factor of $\frac{100}{99}$. Now, taking the parameters of the $L$-reduction of our construction, and based on the result of [[Chlebík]{}]{} and [[Chlebíkov[á]{}]{}]{}, we can show that,

The $k$-anonymization problem cannot be approximated within a factor of $\frac{6238}{6237}$, even when the number of columns in 3 and the privacy parameter is fixed as $k=7$.

MAXSNP-Hardness and Inapproximability Bound
-------------------------------------------

We show that the $k$-anonymization problem is MAXSNP-hard even when the number of columns is 3; meaning it cannot be approximated within a factor of $1+\epsilon$, for some $\epsilon>0$.

\[thm:BBB\] The $k$-anonymization problem is MAXSNP-hard, even when the number of columns in 3 and the privacy parameter is fixed as $k=7$.

[[*Proof:* ]{}]{}The vertex cover problem on 3-regular graphs is known to be MAXSNP-hard [@Alimonti]. We shall argue that the reduction given in Theorem \[thm:AAA\] is an $L$-reduction (see [@Papa] for a discussion on $L$-reductions); it would follow that the $k$-anonymization problem is MAXSNP-hard. Recall that an $L$-reduction from a minimization problem $P_1$ to a minimization problem $P_2$ consists of two polynomial time algorithms $R$ and $S$. The algorithm $R$ 