## 2 Complexity and Algorithms
### Greedy Heuristic  
In this section, we provide a greedy heuristic based on the ideas of the fixed-parameter algorithm of Theorem 3 presented in Section 2.1. The fixed-parameter algorithm basically does an exhaustive search on the assignment of rows to pattern vectors. More precisely, for each row type \(R\) and each pattern vector \(v\) it tries both possibilities of whether rows of \(R\) are assigned to \(v\) or not. Furthermore, in the ILP formulation, all assignments of rows to pattern vectors are possible. In contrast, our greedy heuristic will just pick for each input row type \(R\) the \"cheapest\" pattern vector \(v\) and, then, assigns all compatible rows of \(M\) to \(v\). This is realized as follows: We consider all pattern vectors, one after the other, ordered by increasing number of \(\star\)-symbols. This ensures that we start with the \"cheapest\" pattern vector. Then, we assign as many rows as possible of \(M\) to \(v\): We just consider every instance \(R^{\prime}\) of \(v\), and if there are more than \(k\) rows in \(M\) that are compatible with \(R^{\prime}\), then, we assign all compatible rows to \(R^{\prime}\). Once a row is assigned, it will not be reassigned to any other output row type, and hence, the row will be deletedfrom \(M\). Overall this gives a running time of \(O(pnm)\). See Algorithm 1 for the pseudo-code of the greedy heuristic.If at some point in time, there are less than \(k\) remaining rows in \(M\), then, these rows will be fully suppressed. Note that this slightly deviates from our formal definition of Pattern-Guided \(k\)-Anonymity. However, since fully suppressed rows do not reveal any data, this potential violation of the \(k\)-anonymity requirement does not matter. ```
1:Sort pattern vectors \(P\) by cost (increasing order)
2:for each\(v\in P\)do
3:for each instance \(R^{\prime}\) of \(v\)do
4:if\(\geq k\) rows are compatible with \(R^{\prime}\)then
5: Assign all compatible rows of \(M\) to \(R^{\prime}\)
6: Delete the assigned rows from \(M\). ```  
**Algorithm 1** Greedy Heuristic (\(M,P,k\))  
Our greedy heuristic clearly does not always provide optimal solutions. Our experiments indicate, however, that it is very fast and that it typically provides solutions close to the optimum and outperforms the Mondrian algorithm [21] in most datasets we tested. While this demonstrates the practicality of our heuristic (Algorithm 1), the following result shows that from the viewpoint of polynomial-time approximation algorithmics, it is weak in the worst case. **Theorem 4**. : _Algorithm 1 for Pattern-Guided \(k\)-Anonymity runs in \(O(pnm)\) time and provides a factor \(m\)-approximation. This approximation bound is asymptotically tight for Algorithm 1._  
Proof. : Since the running time is already discussed above, it remains to show the approximation factor. Let \(s_{\text{heur}}\) be the number of suppressions in a solution provided by Algorithm 1 and \(s_{\text{opt}}\) be the number of suppressions in an optimal solution. We show that for every instance, it holds that \(s_{\text{heur}}\leq m\cdot s_{\text{opt}}\). Let \(M\) be a matrix, \(M^{\prime}_{\text{heur}}\) be the suppressed matrix produced by Algorithm 1, and \(M^{\prime}_{\text{opt}}\) be the suppressed matrix corresponding to an optimal solution. First, observe that for any row in \(M^{\prime}_{\text{opt}}\) not containing any suppressed entry, it follows that the corresponding row in \(M^{\prime}_{\text{heur}}\) also does not contain any suppression. Clearly, each row in \(M^{\prime}_{\text{heur}}\) has at most \(m\) entries suppressed. Thus, each row in \(M^{\prime}_{\text{heur}}\) has at most \(m\) times more suppressed entries than the corresponding row in \(M^{\prime}_{\text{opt}}\) and, hence, \(s_{\text{heur}}\leq m\cdot s_{\text{opt}}\). To show that this upper bound is asymptotically tight, consider the following instance. Set \(k=m\), and let \(M\) be as follows: The matrix \(M\) contains \(k\)-times the row with the symbol \(1\) in every entry.