63|C^*|$. Thus, we have $\alpha = 63$. In Theorem \[thm:AAA\], we showed how to construct a vertex cover $C$, from a given $k$-anonymization solution $\sigma$ such that $|C|$ is at most the extra cost of $\sigma$; this construction is our algorithm $S$. It follows that $|C|\leq {{\rm Cost}}(\sigma)-ABC$. We already saw that ${{\rm Cost}}(\sigma^*) \leq ABC + |C^*|$. Combining the two inequalities, we get that $|C|-|C^*|\leq {{\rm Cost}}(\sigma)-{{\rm Cost}}(\sigma^*)$. Thus, we have $\beta = 1$. We have provided an $L$-reduction with $\alpha = 63$ and $\beta=1$. [$\Box$]{}

We next extend the Theorem \[thm:BBB\] to get a mild inapproximability bound.

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$.

[[*Proof:* ]{}]{}Suppose we have an algorithm for solving the $k$-anonymization problem with an approximation ratio of $a$. Using the $L$-reduction given in Theorem \[thm:BBB\], we can obtain an algorithm for the vertex cover problem on 3-regular graphs with an approximation ratio of $(1+\alpha\beta (a-1))$. [[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}$. It follows that the $k$-anonymization problem cannot be approximated 