## 1 Introduction  
Making a matrix \(k\)_-anonymous_, that is, each row has to occur at least \(k\) times, is a classic model for (combinatorial) data privacy [1; 2]. We omit considerations on the also very popular model of \"differential privacy\" [3], which has a more statistical than a combinatorial flavor. It is well-known that there are certain weaknesses of the \(k\)-anonymity concept, for example, when the anonymized data is used multiple times [1]. Here, we focus on \(k\)-anonymity, which, due to its simplicity and good interpretability, continues to be of interest in current applications. The idea behind \(k\)-anonymity is that each row of the matrix represents an individual, and the \(k\)-fold appearance of the corresponding row shall avoid the situation in which the person or object behind can be identified. To reach this goal, clearly, some information loss has to be accepted, that is, some entries of the matrix have to be suppressed (blanked out); in this way, information about certain attributes (represented by the columns of the matrix) is lost. Thus, the natural goal is to minimize this loss of information when transforming an arbitrary data matrix into a \(k\)-anonymous one. The corresponding optimization problem \(k\)-Anonymity is NP-hard (even in special cases) and hard to approximate [4; 5; 6; 7; 8]. Nevertheless, it played a significant role in many applications, thereby mostly relying on heuristic approaches for making a matrix \(k\)-anonymous [2; 9; 10]. It was observed that care has to be taken concerning the \"usefulness\" (also in terms of expressiveness) of the anonymized data [11; 12]. Indeed, depending on the application that has to work on the \(k\)-anonymized data, certain entry suppressions may \"hurt\" less than others. For instance, considering medical data records, the information about eye color may be less informative than information about blood pressure. Hence, it would be useful for the user of the anonymized data to specify information that may help in doing the anonymization process in a more sophisticated way. Thus, in recent work [13], we proposed a \"pattern-guided\" approach to data anonymization, in a way that allows the user to specify which combinations of attributes are less harmful to suppress than others. More specifically, the approach allows \"pattern vectors\", which may be considered as blueprints for the structure of anonymized rows--each row has to be matched with exactly one of the pattern vectors (we will become more precise about this when formally introducing our new model). The corresponding proposed optimization problem [13], however, has the clear weakness that each pattern vector can only be used once, disallowing that there are different incarnations of the very same anonymization pattern. While this might be useful for the clustering perspective of the problem [13], we see no reason to justify this constraint from the viewpoint of data privacy. This leads us to proposing a modified model, whose usefulness for practical data anonymization tasks is supported by experiments on real-world data and comparison with a known \(k\)-anonymization algorithm. Altogether, with our new model, we can improve both on \(k\)-Anonymity by letting the data user influence the anonymization process, as well as on the previous model [13] by allowing full flexibility for the data user to influence the anonymization process. Notably, the previous model is more suitable for homogeneous team formation instead of data anonymization [14]. An extended abstract of this work appeared in the _Proceedings of the Joint Conference of the 7 th International Frontiers of Algorithmics Workshop and the 9 th International Conference on Algorithmic Aspects of Information and Management (FAW-AAIM '13)_, Dalian, China, Volume 7924, of Lecture Notes in Computer Science, pages 350-361, June, 2013. (c) Springer. This full version contains all proof details and an extended experimental section.