within a factor of $\frac{6238}{6237}$. [$\Box$]{}

Special case: $m$ and $|\Sigma|$ are constants
==============================================

As our NP-hardness reduction utilizes alphabets of arbitrarily large size, a natural question is whether the problem remains NP-hard when both the number of columns and the alphabet size are fixed constants. Here, we show that this case can be solved optimally in polynomial time.

In the problem definition, let $m$, the number of columns, to be a constant and let the size of $\Sigma$ be a constant $s$ and let $k$ be the privacy parameter. By a [row pattern]{}, we mean a vector over $m$ columns whose entries belong to $\Sigma$. Let ${{\cal R}}$ denote the set of all row patterns; $|{{\cal R}}| =
|\Sigma|^{m}$ is a constant. By an [*anonymization pattern*]{}, we mean a vector over $m$ columns whose each entry is either a symbol from $\Sigma$ or the suppression symbol ‘$*$’. Let ${{\cal P}}$ denote the set of all anonymization patterns; $|{{\cal P}}| = (|\Sigma|+1)^{m+1}$ is a constant . We say that a row pattern $t$ [*matches*]{} an anonymization pattern $p$, if $p$ and $t$ agree on all columns, except the columns suppressed in $p$. We use “$t\sim p$" as a shorthand to 