In this section we report some common grouping problems **in theoretical computer science and artificial intelligence that share a similar structure with the CSG**
problem.

2.1. Discretization of attributes. **An important problem in knowledge discovery**
and data mining is the discretization of attributes with real values [5, 3]. The discretization process facilitates the extraction of decision rules from a table with real value attributes. As presented in [3] the discretization selects a set of cut points of attributes determining a partition of the real value attributes into intervals. The set of cuts determines a grid in k**-dimensional space with** Qk i=1 ni **regions, where** k is the number of attributes and niis the number of intervals of the i**-th attribute.**
Checking if there is a consistent set of cuts such that the grid defined by them contains at most K **regions in NP-complete [3].**
2.2. Learning Bayesian prototype trees. **In [20] the authors present a method**
to learn Bayesian networks, and specifically Bayesian prototype trees assuming that data form clusters of similar vectors. The data can be partitioned into clusters and the maximum likelihood estimates of the partitioning computed. A data **partition determines the corresponding Bayesian prototype tree model. Hence, given a**
training data set D consisting of N **data vectors, the authors proposed to find the**
optimal Bayesian prototype tree by finding the optimal partition vector among the N N **different vectors.**
2.3. Cluster ensemble problem with graph partitioning. **Clustering and**
graph partitioning are two concepts strongly related. Clustering is **a data analysis**
technique adopted in statistics, data mining, and machine learning communities, involving partitioning a set of instances into a given number of groups **optimising**
an objective function. Recently, cluster ensemble **techniques [27] improve clustering performance by generating multiple partitions of the given data set and then**
combining them to form a superior clustering solution. [27, 7] propose a graph partitioning formulation for cluster ensembles. Given a data set x = {Xi**, . . . , X**n},
a cluster ensemble is a set of clustering solutions, represented as C = {C1**, . . . , C**R}, where R is the ensemble size. Each clustering solution Ci**is a partition of the**
data set into Ki **disjoint clusters. The graph partitioning problem is to partition a**
weighted graph G into K parts by finding K **disjoint clusters of its vertices.** G is characterised by the set V of vertices and by a nonnegative and symmetric similarity matrix W **characterising the similarity between each pair of vertices. The cut**
of a partition P is defined as Cut(P, W) = Pw(i, j), where i and j **are vertices do**
not belonging to the same cluster. The general goal of graph partitioning is to find a partition that maximise the cut.

2.4. Aggregation for Natural Language Generation. Aggregation **represents**
a main component of natural language generation systems. The task is to merge two or more linguistic structures into a single sentence. In [2] the authors presented an automatic tool for performing the semantic grouping task by formalising it as a CSG problem, where each coalition corresponds to a sentence. The strength of the proposed approach lies in its ability to capture global partitioning **constraints**
by performing collective inference over local pairwise assignments. Pairwise constraints capture the semantic compatibility between pairs of linguistic structures