Mean | 0.69 | 0.69 | 0.69 | 0.69 | 0.69 |  0.48∗ | 0.14 | 0.22 |  0.59∗ | 0.64

∗Nan values (–) are replaced with 0 before computing the mean.

Table 27: Average Adjusted Rand Index (ARI) values of five versions of the
PCCC algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS,
LCC) obtained with constraint sets of size 5% CS. Higher values indicate more
overlap with the ground truth assignment. The highest values are stated in
bold. The column KMEANS reports the average ARI values that were obtained with
the unconstrained k-means algorithm. The hyphen indicates that the respective
algorithm returned no solution within the time limit of 3,600 seconds.

| 10% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | CSC | DILS | LCC | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
n500-k2 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.53 | 0.97
n500-k5 | 0.97 | 0.97 | 0.97 | 0.97 | 0.97 | – | 0.03 | 0.77 | 0.92 | 0.77
n500–k10 | 0.90 | 0.90 | 0.92 | 0.91 | 0.91 | 0.81 | 0.01 | 0.24 | 0.77 | 0.87
n500-k20 | 0.61 | 0.61 | 0.62 | 0.61 | 0.61 | 0.54 | 0.00 | 0.08 | 0.52 | 0.56
n500-k50 | 0.39 | 0.39 | 0.39 | 0.39 | 0.39 | 0.38 | 0.00 | 0.03 | 0.40 | 0.38
n500-k100 | 0.22 | 0.22 | 0.22 | 0.22 | 0.22 | 0.22 | 0.00 | 0.01 | 0.22 | 0.22
n1000-k2 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.67 | 0.98
n1000-k5 | 0.99 | 0.99 | 0.83 | 0.99 | 0.99 | 0.96 | 0.20 | 0.64 | 0.88 | 0.86
n1000-k10 | 0.98 | 0.98 | 0.94 | 0.94 | 0.98 | – | 0.01 | 0.09 | 0.77 | 0.80
n1000-k20 | 0.68 | 0.68 | 0.67 | 0.71 | 0.70 | – | 0.00 | 0.04 | 0.50 | 0.57
n1000-k50 | 0.43 | 0.43 | 0.43 | 0.43 | 0.43 | 0.40 | 0.00 | 0.02 | 0.41 | 0.40
n1000-k100 | 0.26 | 0.26 | 0.26 | 0.26 | 0.26 | 0.25 | 0.00 | 0.01 | 0.25 | 0.24
n2000-k2 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.96
n2000-k5 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.71 | 0.20 | 0.94 | 0.77
n2000-k10 | 0.99 | 0.99 | 0.95 | 0.95 | 0.95 | – | 0.03 | 0.01 | 0.64 | 0.83
n2000-k20 | 0.90 | 0.90 | 0.81 | 0.82 | 0.82 | – | 0.01 | 0.01 | 0.51 | 0.59
n2000-k50 | 0.49 | 0.49 | 0.51 | 0.50 | 0.49 | 0.41 | 0.01 | 0.01 | 0.46 | 0.41
n2000-k100 | 0.27 | 0.27 | 0.27 | 0.27 | 0.27 | 0.25 | 0.00 | 0.00 | 0.27 | 0.25
n5000-k2 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | – | 1.00 | 0.40 | – | 0.98
n5000-k5 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | – | 0.73 | 0.00 | – | 0.87
n5000-k10 | 1.00 | 1.00 | 0.96 | 1.00 | 1.00 | – | 0.32 | 0.00 | – | 0.86
n5000-k20 | 0.98 | 0.98 | 0.89 | 0.89 | 0.94 | – | 0.03 | 0.00 | – | 0.59
n5000-k50 | 0.56 | 0.56 | 0.70 | 0.71 | 0.71 | – | 0.01 | 0.00 | 0.41 | 0.42
n5000-k100 | 0.27 | 0.27 | 0.34 | 0.35 | 0.35 | 0.27 | 0.01 | 0.00 | 0.29 | 0.25
Mean | 0.75 | 0.75 | 0.74 | 0.75 | 0.75 |  0.35∗ | 0.26 | 0.23 |  0.47∗ | 0.64

∗Nan values (–) are replaced with 0 before computing the mean.

Table 28: Average Adjusted Rand Index (ARI) values of five versions of the
PCCC algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS,
LCC) obtained with constraint sets of size 10% CS. Higher values indicate more
overlap with the ground truth assignment. The highest values are stated in
bold. The column KMEANS reports the average ARI values that were obtained with
the unconstrained k-means algorithm. The hyphen indicates that the respective
algorithm returned no solution within the time limit of 3,600 seconds.

| 15% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | CSC | DILS | LCC | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
n500-k2 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.97
n500-k5 | 0.99 | 0.99 | 0.92 | 0.91 | 0.99 | 0.99 | 0.43 | 0.88 | 0.92 | 0.77
n500–k10 | 0.98 | 0.98 | 0.90 | 0.90 | 0.88 | – | 0.03 | 0.32 | 0.94 | 0.87
n500-k20 | 0.71 | 0.71 | 0.71 | 0.70 | 0.70 | 0.54 | 0.01 | 0.08 | 0.56 | 0.56
n500-k50 | 0.43 | 0.43 | 0.43 | 0.43 | 0.43 | 0.40 | 0.00 | 0.03 | 0.41 | 0.38
n500-k100 | 0.24 | 0.24 | 0.24 | 0.24 | 0.24 | 0.22 | 0.01 | 0.02 | 0.25 | 0.22
n1000-k2 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | – | 0.98
n1000-k5 | 1.00 | 1.00 | 0.85 | 1.00 | 1.00 | 1.00 | 0.72 | 0.68 | 0.99 | 0.86
n1000-k10 | 0.99 | 0.99 | 0.99 | 0.99 | 0.99 | 1.00 | 0.07 | 0.09 | 0.71 | 0.80
n1000-k20 | 0.89 | 0.89 | 0.81 | 0.81 | 0.82 | – | 0.01 | 0.02 | 0.48 | 0.57
n1000-k50 | 0.51 | 0.51 | 0.51 | 0.50 | 0.52 | 0.41 | 0.01 | 0.01 | 0.46 | 0.40
n1000-k100 | 0.28 | 0.28 | 0.28 | 0.28 | 0.28 | 0.27 | 0.00 | 0.01 | 0.28 | 0.24
n2000-k2 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | – | 1.00 | 1.00 | – | 0.96
n2000-k5 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.73 | 0.23 | 1.00 | 0.77
n2000-k10 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.40 | 0.02 | – | 0.83
n2000-k20 | 0.98 | 0.98 | 0.90 | 0.92 | 0.98 | 0.95 | 0.03 | 0.01 | 0.60 | 0.59
n2000-k50 | 0.46 | 0.46 | 0.66 | 0.68 | 0.68 | – | 0.01 | 0.00 | 0.44 | 0.41
n2000-k100 | 0.04 | 0.04 | 0.34 | 0.33 | 0.33 | 0.29 | 0.01 | 0.00 | 0.30 | 0.25
n5000-k2 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | – | 1.00 | 0.39 | – | 0.98
n5000-k5 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | – | 0.73 | 0.01 | – | 0.87
n5000-k10 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | – | 0.74 | 0.00 | – | 0.86
n5000-k20 | 1.00 | 1.00 | 0.92 | 0.92 | 1.00 | 1.00 | 0.08 | 0.00 | – | 0.59
n5000-k50 | 0.75 | 0.75 | 0.84 | 0.88 | 0.90 | – | 0.02 | 0.00 | – | 0.42
n5000-k100 | 0.40 | 0.40 | 0.57 | 0.61 | 0.63 | – | 0.01 | 0.00 | 0.34 | 0.25
Mean | 0.78 | 0.78 | 0.79 | 0.80 | 0.81 |  0.46∗ | 0.33 | 0.24 |  0.40∗ | 0.64

∗Nan values (–) are replaced with 0 before computing the mean.

Table 29: Average Adjusted Rand Index (ARI) values of five versions of the
PCCC algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS,
LCC) obtained with constraint sets of size 15% CS. Higher values indicate more
overlap with the ground truth assignment. The highest values are stated in
bold. The column KMEANS reports the average ARI values that were obtained with
the unconstrained k-means algorithm. The hyphen indicates that the respective
algorithm returned no solution within the time limit of 3,600 seconds.

| 20% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | CSC | DILS | LCC | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
n500-k2 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.97
n500-k5 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.68 | 0.90 | 0.99 | 0.77
n500–k10 | 0.99 | 0.99 | 0.99 | 0.99 | 0.99 | 0.97 | 0.07 | 0.44 | 0.73 | 0.87
n500-k20 | 0.85 | 0.85 | 0.76 | 0.78 | 0.80 | – | 0.02 | 0.08 | 0.61 | 0.56
n500-k50 | 0.48 | 0.48 | 0.46 | 0.48 | 0.48 | 0.45 | 0.01 | 0.04 | 0.43 | 0.38
n500-k100 | 0.26 | 0.26 | 0.25 | 0.25 | 0.25 | 0.24 | 0.01 | 0.02 | 0.26 | 0.22
n1000-k2 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | – | 0.98
n1000-k5 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.73 | 0.67 | 1.00 | 0.86
n1000-k10 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.36 | 0.15 | 0.87 | 0.80
n1000-k20 | 0.96 | 0.96 | 0.87 | 0.89 | 0.93 | – | 0.03 | 0.02 | 0.63 | 0.57
n1000-k50 | 0.67 | 0.67 | 0.62 | 0.66 | 0.67 | – | 0.01 | 0.01 | 0.46 | 0.40
n1000-k100 | 0.32 | 0.32 | 0.32 | 0.32 | 0.32 | 0.30 | 0.01 | 0.01 | 0.30 | 0.24
n2000-k2 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | – | 1.00 | 1.00 | – | 0.96
n2000-k5 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.73 | 0.21 | – | 0.77
n2000-k10 | 1.00 | 1.00 | 0.93 | 1.00 | 1.00 | 1.00 | 0.76 | 0.02 | 0.93 | 0.83
n2000-k20 | 1.00 | 1.00 | 0.89 | 0.96 | 1.00 | 1.00 | 0.04 | 0.00 | 0.72 | 0.59
n2000-k50 | 0.57 | 0.57 | 0.77 | 0.80 | 0.82 | – | 0.02 | 0.00 | 0.53 | 0.41
n2000-k100 | 0.35 | 0.35 | 0.46 | 0.48 | 0.49 | 0.38 | 0.01 | 0.00 | 0.35 | 0.25
n5000-k2 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | – | 1.00 | 0.41 | – | 0.98
n5000-k5 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | – | 0.82 | 0.01 | – | 0.87
n5000-k10 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | – | 0.75 | 0.00 | – | 0.86
n5000-k20 | 1.00 | 1.00 | 0.95 | 1.00 | 1.00 | – | 0.24 | 0.00 | – | 0.59
n5000-k50 | 0.99 | 0.99 | 0.93 | 0.95 | 0.99 | 0.99 | 0.02 | 0.00 | – | 0.42
n5000-k100 | – | – | 0.75 | 0.78 | 0.81 | – | 0.02 | 0.00 | – | 0.25
Mean |  0.81∗ |  0.81∗ | 0.83 | 0.85 | 0.86 |  0.47∗ | 0.39 | 0.25 |  0.41∗ | 0.64

∗Nan values (–) are replaced with 0 before computing the mean.

Table 30: Average Adjusted Rand Index (ARI) values of five versions of the
PCCC algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS,
LCC) obtained with constraint sets of size 20% CS. Higher values indicate more
overlap with the ground truth assignment. The highest values are stated in
bold. The column KMEANS reports the average ARI values that were obtained with
the unconstrained k-means algorithm. The hyphen indicates that the respective
algorithm returned no solution within the time limit of 3,600 seconds.

| 0% CS |  |
---|---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | CSC | DILS | LCC | KMEANS | GT
Dataset |  |  |  |  |  |  |  |  |  |  |
n500-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | – | 0.54 | 0.54
n500-k5 | 0.70 | 0.70 | 0.70 | 0.70 | 0.70 | 0.70 | 0.67 | 0.58 | – | 0.70 | 0.61
n500–k10 | 0.56 | 0.56 | 0.56 | 0.56 | 0.56 | 0.50 | 0.54 | 0.10 | – | 0.56 | 0.50
n500-k20 | 0.39 | 0.39 | 0.39 | 0.39 | 0.39 | 0.38 | 0.36 | -0.17 | – | 0.39 | 0.21
n500-k50 | 0.37 | 0.37 | 0.37 | 0.37 | 0.37 | 0.37 | 0.34 | -0.45 | – | 0.37 | 0.07
n500-k100 | 0.37 | 0.37 | 0.37 | 0.37 | 0.37 | 0.34 | 0.33 | -0.65 | – | 0.37 | -0.11
n1000-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | – | 0.54 | 0.54
n1000-k5 | 0.66 | 0.66 | 0.66 | 0.66 | 0.66 | 0.69 | 0.66 | 0.38 | – | 0.66 | 0.60
n1000-k10 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.54 | 0.55 | -0.01 | – | 0.55 | 0.51
n1000-k20 | 0.39 | 0.39 | 0.39 | 0.39 | 0.39 | 0.38 | 0.35 | -0.19 | – | 0.39 | 0.24
n1000-k50 | 0.36 | 0.36 | 0.36 | 0.36 | 0.36 | 0.36 | 0.34 | -0.36 | – | 0.36 | 0.10
n1000-k100 | 0.37 | 0.37 | 0.37 | 0.37 | 0.37 | 0.35 | 0.34 | -0.47 | – | 0.37 | -0.06
n2000-k2 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | – | 0.55 | 0.55
n2000-k5 | 0.70 | 0.70 | 0.70 | 0.70 | 0.70 | 0.67 | 0.67 | 0.08 | – | 0.70 | 0.60
n2000-k10 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.54 | 0.56 | -0.12 | – | 0.55 | 0.51
n2000-k20 | 0.39 | 0.39 | 0.39 | 0.39 | 0.39 | 0.38 | 0.35 | -0.20 | – | 0.39 | 0.24
n2000-k50 | 0.35 | 0.35 | 0.35 | 0.35 | 0.35 | 0.36 | 0.34 | -0.29 | – | 0.35 | 0.10
n2000-k100 | 0.34 | 0.34 | 0.34 | 0.34 | 0.34 | 0.33 | 0.34 | -0.35 | – | 0.34 | -0.05
n5000-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.33 | – | 0.54 | 0.54
n5000-k5 | 0.67 | 0.67 | 0.67 | 0.67 | 0.67 | 0.68 | 0.67 | -0.10 | – | 0.67 | 0.60
n5000-k10 | 0.57 | 0.57 | 0.57 | 0.57 | 0.57 | 0.54 | 0.55 | -0.13 | – | 0.57 | 0.51
n5000-k20 | 0.38 | 0.38 | 0.38 | 0.38 | 0.38 | 0.38 | 0.34 | -0.14 | – | 0.38 | 0.23
n5000-k50 | 0.35 | 0.35 | 0.35 | 0.35 | 0.35 | 0.34 | 0.32 | -0.16 | – | 0.35 | 0.10
n5000-k100 | 0.34 | 0.34 | 0.34 | 0.34 | 0.34 | 0.33 | 0.32 | -0.23 | – | 0.34 | -0.05
Mean | 0.48 | 0.48 | 0.48 | 0.48 | 0.48 | 0.47 | 0.46 | -0.04 |  -1.00∗ | 0.48 | 0.32

∗Nan values (–) are replaced with -1 before computing the mean.

Table 31: Average Silhouette coefficients of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC)
obtained with constraint sets of size 0% CS. Higher values indicate better
separated clusters. The highest values are stated in bold. The column KMEANS
reports the average Silhouette coefficients that were obtained with the
unconstrained k-means algorithm. The column GT reports the Silhouette
coefficients of the ground truth assignment. The hyphen indicates that the
respective algorithm returned no solution within the time limit of 3,600
seconds. We noticed that the LCC algorithm stops with a runtime error when the
constraint set is empty. This is why the LCC algorithm did not return any
solutions for the constraint sets of size 0% CS.

| 5% CS |  |
---|---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | CSC | DILS | LCC | KMEANS | GT
Dataset |  |  |  |  |  |  |  |  |  |  |
n500-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | – | -0.15 | 0.51 | 0.54 | 0.54 | 0.54
n500-k5 | 0.65 | 0.65 | 0.66 | 0.66 | 0.64 | 0.60 | -0.17 | 0.32 | 0.49 | 0.70 | 0.61
n500–k10 | 0.53 | 0.53 | 0.56 | 0.56 | 0.55 | 0.45 | -0.41 | -0.07 | 0.52 | 0.56 | 0.50
n500-k20 | 0.39 | 0.39 | 0.39 | 0.39 | 0.39 | 0.36 | -0.53 | -0.21 | 0.35 | 0.39 | 0.21
n500-k50 | 0.37 | 0.37 | 0.37 | 0.37 | 0.37 | 0.36 | -0.72 | -0.45 | 0.35 | 0.37 | 0.07
n500-k100 | 0.34 | 0.34 | 0.34 | 0.34 | 0.34 | 0.32 | -0.73 | -0.64 | 0.31 | 0.37 | -0.11
n1000-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.53 | 0.54 | 0.54 | 0.54
n1000-k5 | 0.63 | 0.63 | 0.63 | 0.63 | 0.63 | – | -0.45 | 0.13 | 0.59 | 0.66 | 0.60
n1000-k10 | 0.53 | 0.53 | 0.55 | 0.55 | 0.54 | 0.50 | -0.34 | -0.11 | 0.44 | 0.55 | 0.51
n1000-k20 | 0.36 | 0.36 | 0.36 | 0.36 | 0.36 | 0.35 | -0.37 | -0.23 | 0.33 | 0.39 | 0.24
n1000-k50 | 0.34 | 0.34 | 0.34 | 0.34 | 0.34 | 0.32 | -0.70 | -0.33 | 0.34 | 0.36 | 0.10
n1000-k100 | 0.36 | 0.36 | 0.36 | 0.36 | 0.36 | 0.34 | -0.77 | -0.47 | – | 0.37 | -0.06
n2000-k2 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.29 | 0.55 | 0.55
n2000-k5 | 0.62 | 0.62 | 0.62 | 0.62 | 0.62 | 0.62 | -0.23 | -0.09 | 0.51 | 0.70 | 0.60
n2000-k10 | 0.48 | 0.48 | 0.56 | 0.55 | 0.53 | 0.49 | -0.31 | -0.16 | 0.48 | 0.55 | 0.51
n2000-k20 | 0.32 | 0.32 | 0.32 | 0.32 | 0.32 | 0.29 | -0.30 | -0.19 | 0.32 | 0.39 | 0.24
n2000-k50 | 0.31 | 0.31 | 0.31 | 0.31 | 0.31 | 0.30 | -0.57 | -0.26 | 0.32 | 0.35 | 0.10
n2000-k100 | 0.31 | 0.31 | 0.31 | 0.30 | 0.31 | 0.30 | -0.78 | -0.33 | 0.24 | 0.34 | -0.05
n5000-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | – | 0.54 | 0.25 | 0.51 | 0.54 | 0.54
n5000-k5 | 0.61 | 0.61 | 0.61 | 0.61 | 0.61 | 0.59 | 0.14 | -0.06 | 0.54 | 0.67 | 0.60
n5000-k10 | 0.51 | 0.51 | 0.51 | 0.51 | 0.51 | – | -0.10 | -0.06 | 0.07 | 0.57 | 0.51
n5000-k20 | 0.27 | 0.27 | 0.28 | 0.26 | 0.27 | – | -0.13 | -0.10 | 0.18 | 0.38 | 0.23
n5000-k50 | 0.26 | 0.26 | 0.27 | 0.26 | 0.26 | 0.22 | -0.22 | -0.14 | 0.25 | 0.35 | 0.10
n5000-k100 | 0.26 | 0.26 | 0.26 | 0.26 | 0.26 | 0.24 | -0.54 | -0.20 | 0.25 | 0.34 | -0.05
Mean | 0.44 | 0.44 | 0.45 | 0.45 | 0.44 |  0.11∗ | -0.28 | -0.08 |  0.32∗ | 0.48 | 0.32

∗Nan values (–) are replaced with -1 before computing the mean.

Table 32: Average Silhouette coefficients of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC)
obtained with constraint sets of size 5% CS. Higher values indicate better
separated clusters. The highest values are stated in bold. The column KMEANS
reports the average Silhouette coefficients that were obtained with the
unconstrained k-means algorithm. The column GT reports the Silhouette
coefficients of the ground truth assignment. The hyphen indicates that the
respective algorithm returned no solution within the time limit of 3,600
seconds.

| 10% CS |  |
---|---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | CSC | DILS | LCC | KMEANS | GT
Dataset |  |  |  |  |  |  |  |  |  |  |
n500-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.30 | 0.54 | 0.54
n500-k5 | 0.62 | 0.62 | 0.62 | 0.62 | 0.62 | – | -0.24 | 0.42 | 0.62 | 0.70 | 0.61
n500–k10 | 0.50 | 0.50 | 0.53 | 0.53 | 0.53 | 0.44 | -0.34 | -0.06 | 0.40 | 0.56 | 0.50
n500-k20 | 0.33 | 0.33 | 0.34 | 0.33 | 0.33 | 0.30 | -0.43 | -0.26 | 0.29 | 0.39 | 0.21
n500-k50 | 0.33 | 0.33 | 0.33 | 0.33 | 0.33 | 0.29 | -0.67 | -0.42 | 0.27 | 0.37 | 0.07
n500-k100 | 0.34 | 0.34 | 0.34 | 0.34 | 0.34 | 0.30 | -0.74 | -0.65 | 0.27 | 0.37 | -0.11
n1000-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.33 | 0.54 | 0.54
n1000-k5 | 0.60 | 0.60 | 0.62 | 0.60 | 0.60 | 0.58 | -0.16 | 0.29 | 0.53 | 0.66 | 0.60
n1000-k10 | 0.52 | 0.52 | 0.53 | 0.52 | 0.52 | – | -0.16 | -0.16 | 0.38 | 0.55 | 0.51
n1000-k20 | 0.28 | 0.28 | 0.29 | 0.29 | 0.28 | – | -0.33 | -0.22 | 0.20 | 0.39 | 0.24
n1000-k50 | 0.28 | 0.28 | 0.29 | 0.28 | 0.28 | 0.26 | -0.64 | -0.33 | 0.26 | 0.36 | 0.10
n1000-k100 | 0.29 | 0.29 | 0.30 | 0.29 | 0.29 | 0.27 | -0.73 | -0.44 | 0.26 | 0.37 | -0.06
n2000-k2 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55
n2000-k5 | 0.61 | 0.61 | 0.61 | 0.61 | 0.61 | 0.61 | 0.62 | -0.03 | 0.57 | 0.70 | 0.60
n2000-k10 | 0.51 | 0.51 | 0.52 | 0.52 | 0.51 | – | -0.22 | -0.12 | 0.18 | 0.55 | 0.51
n2000-k20 | 0.27 | 0.27 | 0.26 | 0.25 | 0.24 | – | -0.17 | -0.18 | 0.10 | 0.39 | 0.24
n2000-k50 | 0.21 | 0.21 | 0.24 | 0.22 | 0.22 | 0.17 | -0.32 | -0.24 | 0.21 | 0.35 | 0.10
n2000-k100 | 0.23 | 0.23 | 0.24 | 0.23 | 0.23 | 0.19 | -0.60 | -0.32 | 0.22 | 0.34 | -0.05
n5000-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | – | 0.54 | 0.24 | – | 0.54 | 0.54
n5000-k5 | 0.60 | 0.60 | 0.60 | 0.60 | 0.60 | – | 0.63 | -0.04 | – | 0.67 | 0.60
n5000-k10 | 0.51 | 0.51 | 0.50 | 0.51 | 0.51 | – | -0.18 | -0.05 | – | 0.57 | 0.51
n5000-k20 | 0.24 | 0.24 | 0.23 | 0.23 | 0.22 | – | -0.18 | -0.07 | – | 0.38 | 0.23
n5000-k50 | 0.03 | 0.03 | 0.15 | 0.14 | 0.14 | – | -0.24 | -0.12 | 0.02 | 0.35 | 0.10
n5000-k100 | 0.03 | 0.03 | 0.12 | 0.10 | 0.10 | 0.03 | -0.44 | -0.18 | 0.08 | 0.34 | -0.05
Mean | 0.40 | 0.40 | 0.41 | 0.40 | 0.40 |  -0.21∗ | -0.14 | -0.05 |  0.08∗ | 0.48 | 0.32

∗Nan values (–) are replaced with -1 before computing the mean.

Table 33: Average Silhouette coefficients of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC)
obtained with constraint sets of size 10% CS. Higher values indicate better
separated clusters. The highest values are stated in bold. The column KMEANS
reports the average Silhouette coefficients that were obtained with the
unconstrained k-means algorithm. The column GT reports the Silhouette
coefficients of the ground truth assignment. The hyphen indicates that the
respective algorithm returned no solution within the time limit of 3,600
seconds.

| 15% CS |  |
---|---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | CSC | DILS | LCC | KMEANS | GT
Dataset |  |  |  |  |  |  |  |  |  |  |
n500-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54
n500-k5 | 0.62 | 0.62 | 0.64 | 0.62 | 0.62 | 0.62 | 0.05 | 0.50 | 0.56 | 0.70 | 0.61
n500–k10 | 0.50 | 0.50 | 0.53 | 0.53 | 0.50 | – | -0.22 | -0.04 | 0.49 | 0.56 | 0.50
n500-k20 | 0.26 | 0.26 | 0.26 | 0.26 | 0.26 | 0.18 | -0.29 | -0.24 | 0.22 | 0.39 | 0.21
n500-k50 | 0.27 | 0.27 | 0.28 | 0.28 | 0.28 | 0.25 | -0.64 | -0.45 | 0.25 | 0.37 | 0.07
n500-k100 | 0.28 | 0.28 | 0.29 | 0.28 | 0.28 | 0.25 | -0.72 | -0.66 | 0.25 | 0.37 | -0.11
n1000-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | – | 0.54 | 0.54
n1000-k5 | 0.60 | 0.60 | 0.62 | 0.60 | 0.60 | 0.60 | 0.63 | 0.31 | 0.59 | 0.66 | 0.60
n1000-k10 | 0.51 | 0.51 | 0.51 | 0.51 | 0.51 | 0.51 | -0.23 | -0.16 | 0.29 | 0.55 | 0.51
n1000-k20 | 0.26 | 0.26 | 0.25 | 0.25 | 0.24 | – | -0.23 | -0.21 | 0.06 | 0.39 | 0.24
n1000-k50 | 0.20 | 0.20 | 0.22 | 0.21 | 0.21 | 0.12 | -0.50 | -0.33 | 0.19 | 0.36 | 0.10
n1000-k100 | 0.24 | 0.24 | 0.25 | 0.24 | 0.24 | 0.19 | -0.69 | -0.49 | 0.22 | 0.37 | -0.06
n2000-k2 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | – | 0.55 | 0.55 | – | 0.55 | 0.55
n2000-k5 | 0.60 | 0.60 | 0.60 | 0.60 | 0.60 | 0.60 | 0.64 | -0.01 | 0.60 | 0.70 | 0.60
n2000-k10 | 0.51 | 0.51 | 0.51 | 0.51 | 0.51 | 0.51 | 0.02 | -0.13 | – | 0.55 | 0.51
n2000-k20 | 0.25 | 0.25 | 0.25 | 0.24 | 0.25 | 0.23 | -0.19 | -0.14 | 0.02 | 0.39 | 0.24
n2000-k50 | -0.05 | -0.05 | 0.15 | 0.14 | 0.14 | – | -0.34 | -0.20 | 0.06 | 0.35 | 0.10
n2000-k100 | -0.30 | -0.30 | 0.14 | 0.14 | 0.13 | 0.07 | -0.55 | -0.32 | 0.11 | 0.34 | -0.05
n5000-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | – | 0.54 | 0.24 | – | 0.54 | 0.54
n5000-k5 | 0.60 | 0.60 | 0.60 | 0.60 | 0.60 | – | 0.63 | -0.06 | – | 0.67 | 0.60
n5000-k10 | 0.51 | 0.51 | 0.51 | 0.51 | 0.51 | – | 0.25 | -0.06 | – | 0.57 | 0.51
n5000-k20 | 0.23 | 0.23 | 0.21 | 0.21 | 0.23 | 0.23 | -0.37 | -0.06 | – | 0.38 | 0.23
n5000-k50 | -0.06 | -0.06 | 0.11 | 0.10 | 0.10 | – | -0.29 | -0.12 | – | 0.35 | 0.10
n5000-k100 | -0.19 | -0.19 | 0.01 | -0.00 | -0.01 | – | -0.45 | -0.19 | -0.08 | 0.34 | -0.05
Mean | 0.33 | 0.33 | 0.38 | 0.38 | 0.37 |  -0.15∗ | -0.06 | -0.05 |  -0.15∗ | 0.48 | 0.32

∗Nan values (–) are replaced with -1 before computing the mean.

Table 34: Average Silhouette coefficients of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC)
obtained with constraint sets of size 15% CS. Higher values indicate better
separated clusters. The highest values are stated in bold. The column KMEANS
reports the average Silhouette coefficients that were obtained with the
unconstrained k-means algorithm. The column GT reports the Silhouette
coefficients of the ground truth assignment. The hyphen indicates that the
respective algorithm returned no solution within the time limit of 3,600
seconds.

| 20% CS |  |
---|---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | CSC | DILS | LCC | KMEANS | GT
Dataset |  |  |  |  |  |  |  |  |  |  |
n500-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54
n500-k5 | 0.61 | 0.61 | 0.61 | 0.61 | 0.61 | 0.61 | 0.58 | 0.51 | 0.61 | 0.70 | 0.61
n500–k10 | 0.50 | 0.50 | 0.50 | 0.50 | 0.50 | 0.50 | -0.21 | 0.04 | 0.29 | 0.56 | 0.50
n500-k20 | 0.26 | 0.26 | 0.26 | 0.26 | 0.25 | – | -0.34 | -0.26 | 0.15 | 0.39 | 0.21
n500-k50 | 0.22 | 0.22 | 0.23 | 0.23 | 0.22 | 0.16 | -0.59 | -0.43 | 0.19 | 0.37 | 0.07
n500-k100 | 0.23 | 0.23 | 0.24 | 0.23 | 0.23 | 0.18 | -0.70 | -0.63 | 0.19 | 0.37 | -0.11
n1000-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | – | 0.54 | 0.54
n1000-k5 | 0.60 | 0.60 | 0.60 | 0.60 | 0.60 | 0.60 | 0.64 | 0.30 | 0.60 | 0.66 | 0.60
n1000-k10 | 0.51 | 0.51 | 0.51 | 0.51 | 0.51 | 0.51 | -0.06 | -0.11 | 0.38 | 0.55 | 0.51
n1000-k20 | 0.25 | 0.25 | 0.24 | 0.23 | 0.24 | – | -0.24 | -0.20 | 0.08 | 0.39 | 0.24
n1000-k50 | 0.15 | 0.15 | 0.17 | 0.16 | 0.15 | – | -0.45 | -0.30 | 0.10 | 0.36 | 0.10
n1000-k100 | 0.16 | 0.16 | 0.18 | 0.17 | 0.16 | 0.11 | -0.64 | -0.45 | 0.13 | 0.37 | -0.06
n2000-k2 | 0.55 | 0.55 | 0.55 | 0.55 | 0.55 | – | 0.55 | 0.55 | – | 0.55 | 0.55
n2000-k5 | 0.60 | 0.60 | 0.60 | 0.60 | 0.60 | 0.60 | 0.64 | -0.04 | – | 0.70 | 0.60
n2000-k10 | 0.51 | 0.51 | 0.55 | 0.51 | 0.51 | 0.51 | 0.33 | -0.15 | 0.44 | 0.55 | 0.51
n2000-k20 | 0.24 | 0.24 | 0.23 | 0.23 | 0.24 | 0.24 | -0.27 | -0.13 | 0.04 | 0.39 | 0.24
n2000-k50 | -0.18 | -0.18 | 0.11 | 0.10 | 0.09 | – | -0.30 | -0.21 | -0.01 | 0.35 | 0.10
n2000-k100 | -0.09 | -0.09 | 0.06 | 0.05 | 0.04 | -0.04 | -0.57 | -0.30 | 0.01 | 0.34 | -0.05
n5000-k2 | 0.54 | 0.54 | 0.54 | 0.54 | 0.54 | – | 0.54 | 0.25 | – | 0.54 | 0.54
n5000-k5 | 0.60 | 0.60 | 0.60 | 0.60 | 0.60 | – | 0.62 | -0.07 | – | 0.67 | 0.60
n5000-k10 | 0.51 | 0.51 | 0.51 | 0.51 | 0.51 | – | 0.26 | -0.06 | – | 0.57 | 0.51
n5000-k20 | 0.23 | 0.23 | 0.23 | 0.23 | 0.23 | – | -0.28 | -0.07 | – | 0.38 | 0.23
n5000-k50 | 0.10 | 0.10 | 0.10 | 0.10 | 0.11 | 0.10 | -0.30 | -0.12 | – | 0.35 | 0.10
n5000-k100 | – | – | -0.03 | -0.04 | -0.04 | – | -0.43 | -0.16 | – | 0.34 | -0.05
Mean |  0.30∗ |  0.30∗ | 0.36 | 0.36 | 0.36 |  -0.20∗ | -0.01 | -0.04 |  -0.22∗ | 0.48 | 0.32

∗Nan values (–) are replaced with -1 before computing the mean.

Table 35: Average Silhouette coefficients of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC)
obtained with constraint sets of size 20% CS. Higher values indicate better
separated clusters. The highest values are stated in bold. The column KMEANS
reports the average Silhouette coefficients that were obtained with the
unconstrained k-means algorithm. The column GT reports the Silhouette
coefficients of the ground truth assignment. The hyphen indicates that the
respective algorithm returned no solution within the time limit of 3,600
seconds.

| 0% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | CSC | DILS | LCC | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
n500-k2 | 0.3 | 0.6 | 0.3 | 0.4 | 0.4 | 0.1 | 2.7 | 2,718.1 | – | 0.3
n500-k5 | 0.6 | 0.5 | 0.5 | 0.6 | 0.7 | 0.1 | 2.9 | 2,459.8 | – | 0.2
n500–k10 | 1.5 | 0.5 | 0.5 | 0.7 | 1.0 | 0.3 | 3.2 | 2,414.0 | – | 0.5
n500-k20 | 4.3 | 0.8 | 0.9 | 1.1 | 1.6 | 0.6 | 3.0 | 2,484.1 | – | 0.3
n500-k50 | 7.7 | 0.6 | 0.6 | 1.0 | 1.1 | 2.6 | 11.0 | 2,313.2 | – | 0.2
n500-k100 | 11.0 | 1.2 | 0.6 | 0.7 | 1.1 | 8.7 | 4.2 | 2,307.5 | – | 0.5
n1000-k2 | 0.8 | 0.7 | 0.8 | 0.7 | 0.8 | 0.1 | 25.0 | 3,639.8 | – | 0.2
n1000-k5 | 2.0 | 1.3 | 1.2 | 1.7 | 2.3 | 0.2 | 27.8 | 3,614.3 | – | 0.2
n1000-k10 | 3.4 | 0.9 | 1.1 | 1.6 | 2.0 | 0.6 | 27.1 | 3,614.5 | – | 0.2
n1000-k20 | 8.3 | 1.7 | 1.5 | 2.0 | 2.5 | 1.7 | 31.5 | 3,618.3 | – | 0.2
n1000-k50 | 24.4 | 1.9 | 1.8 | 2.6 | 3.6 | 5.7 | 32.1 | 3,614.9 | – | 0.2
n1000-k100 | 26.8 | 1.8 | 1.4 | 1.6 | 2.1 | 18.3 | 34.1 | 3,617.5 | – | 0.6
n2000-k2 | 1.3 | 1.5 | 1.4 | 1.4 | 1.3 | 0.2 | 243.1 | 3,682.0 | – | 0.2
n2000-k5 | 4.0 | 2.5 | 2.3 | 3.0 | 4.2 | 0.4 | 258.7 | 3,675.7 | – | 0.4
n2000-k10 | 8.4 | 2.2 | 2.4 | 3.2 | 4.6 | 1.2 | 259.6 | 3,651.8 | – | 0.4
n2000-k20 | 18.0 | 3.2 | 2.9 | 4.3 | 5.8 | 3.8 | 262.5 | 3,609.1 | – | 0.5
n2000-k50 | 59.4 | 3.8 | 4.0 | 5.4 | 7.6 | 11.9 | 268.8 | 3,663.2 | – | 0.5
n2000-k100 | 77.7 | 2.6 | 2.8 | 3.8 | 5.1 | 39.9 | 271.6 | 3,631.1 | – | 0.6
n5000-k2 | 3.6 | 2.7 | 3.0 | 3.0 | 3.0 | 0.7 | 3,269.0 | 3,869.5 | – | 0.5
n5000-k5 | 9.9 | 4.3 | 4.8 | 6.1 | 9.2 | 1.4 | 3,462.1 | 3,771.3 | – | 0.5
n5000-k10 | 14.8 | 3.7 | 4.1 | 5.3 | 8.0 | 3.3 | 3,682.9 | 3,746.6 | – | 0.4
n5000-k20 | 81.2 | 10.9 | 11.6 | 17.3 | 25.4 | 9.8 | 3,633.0 | 3,685.8 | – | 0.9
n5000-k50 | 200.9 | 11.4 | 12.2 | 17.7 | 25.9 | 41.3 | 3,499.3 | 3,718.3 | – | 0.9
n5000-k100 | 458.2 | 11.9 | 13.1 | 19.0 | 28.1 | 105.8 | 3,609.3 | 3,731.3 | – | 1.1
Sum | 1,028.7 | 73.2 | 75.9 | 104.2 | 147.6 | 258.5 | 22,924.5 | 80,851.8 |  86,400.0∗ | 10.6

∗Nan values (–) are replaced with 3,600 before computing the sum.

Table 36: Average running times (in seconds) of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC) for
the constraint sets of size 0% CS. The lowest values are stated in bold. The
column KMEANS reports the average running time of the unconstrained k-means
algorithm. The hyphen indicates that the respective algorithm returned no
solution within the time limit of 3,600 seconds. We noticed that the LCC
algorithm stops with a runtime error when the constraint set is empty. This is
why the LCC algorithm did not return any solutions for the constraint sets of
size 0% CS.

| 5% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | CSC | DILS | LCC | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
n500-k2 | 0.4 | 0.5 | 0.5 | 0.5 | 0.7 | – | 2.9 | 3,039.7 | 8.2 | 0.3
n500-k5 | 1.4 | 1.4 | 0.7 | 0.9 | 1.3 | 0.1 | 2.9 | 2,506.3 | 20.2 | 0.1
n500–k10 | 3.3 | 2.0 | 0.6 | 0.8 | 1.1 | 0.3 | 2.7 | 2,549.4 | 28.7 | 0.1
n500-k20 | 8.1 | 2.2 | 1.1 | 1.3 | 1.8 | 0.6 | 3.0 | 2,441.9 | 47.1 | 0.1
n500-k50 | 10.3 | 1.4 | 0.7 | 0.8 | 1.3 | 2.6 | 3.7 | 2,507.1 | 108.4 | 0.1
n500-k100 | 17.6 | 1.1 | 0.8 | 0.7 | 1.0 | 8.6 | 2.7 | 2,411.4 | 210.6 | 0.2
n1000-k2 | 0.5 | 0.4 | 0.8 | 0.8 | 0.9 | 4.2 | 23.4 | 3,612.9 | 165.3 | 0.1
n1000-k5 | 2.8 | 2.2 | 1.3 | 1.6 | 2.2 | – | 22.9 | 3,617.4 | 37.3 | 0.1
n1000-k10 | 5.6 | 5.3 | 1.1 | 1.5 | 2.4 | 0.5 | 24.4 | 3,606.4 | 63.3 | 0.2
n1000-k20 | 20.9 | 19.1 | 2.2 | 2.5 | 3.7 | 1.8 | 22.9 | 3,620.8 | 104.2 | 0.1
n1000-k50 | 53.2 | 8.3 | 1.9 | 2.4 | 3.6 | 6.0 | 24.9 | 3,611.6 | 232.5 | 0.2
n1000-k100 | 73.1 | 5.5 | 1.5 | 1.9 | 2.7 | 18.6 | 25.5 | 3,630.2 | – | 0.2
n2000-k2 | 0.6 | 0.7 | 0.7 | 0.6 | 0.7 | 503.5 | 263.6 | 3,716.9 | 3,669.7 | 0.3
n2000-k5 | 5.5 | 5.3 | 1.6 | 2.4 | 4.5 | 3.0 | 267.3 | 3,661.7 | 403.9 | 0.2
n2000-k10 | 12.2 | 10.7 | 2.6 | 3.7 | 6.5 | 1.2 | 270.6 | 3,651.1 | 136.2 | 0.4
n2000-k20 | 109.0 | 105.6 | 5.1 | 6.8 | 13.2 | 3.6 | 280.1 | 3,646.3 | 254.1 | 0.2
n2000-k50 | 182.6 | 81.7 | 3.2 | 4.9 | 7.9 | 14.3 | 277.3 | 3,615.8 | 537.3 | 0.7
n2000-k100 | 414.7 | 56.3 | 3.9 | 4.5 | 7.0 | 41.4 | 270.1 | 3,627.7 | 1,006.2 | 0.4
n5000-k2 | 0.8 | 0.7 | 0.7 | 0.7 | 0.5 | – | 2,764.0 | 4,006.1 | 3,793.6 | 0.4
n5000-k5 | 6.3 | 6.0 | 1.7 | 2.0 | 3.9 | 5,929.3 | 2,770.6 | 3,815.8 | 3,802.6 | 0.3
n5000-k10 | 75.5 | 70.1 | 2.7 | 4.2 | 10.2 | – | 2,696.5 | 3,860.4 | 3,863.2 | 0.5
n5000-k20 | 443.5 | 433.5 | 10.2 | 15.6 | 36.6 | – | 2,733.4 | 3,772.5 | 2,310.8 | 0.4
n5000-k50 | 2,600.7 | 2,604.5 | 14.8 | 22.4 | 33.5 | 45.0 | 2,730.1 | 3,813.6 | 2,283.4 | 0.6
n5000-k100 | 3,607.3 | 3,318.0 | 14.0 | 16.9 | 30.3 | 116.9 | 2,639.6 | 3,759.0 | 3,608.7 | 0.6
Sum | 7,656.0 | 6,742.7 | 74.3 | 100.6 | 177.4 |  24,701.6∗ | 18,125.0 | 82,102.0 |  30,295.4∗ | 6.9

∗Nan values (–) are replaced with 3,600 before computing the sum.

Table 37: Average running times (in seconds) of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC) for
the constraint sets of size 5% CS. The lowest values are stated in bold. The
column KMEANS reports the average running time of the unconstrained k-means
algorithm. The hyphen indicates that the respective algorithm returned no
solution within the time limit of 3,600 seconds.

| 10% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | CSC | DILS | LCC | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
n500-k2 | 0.3 | 0.6 | 0.3 | 0.5 | 0.5 | 7.8 | 4.2 | 3,370.1 | 197.6 | 0.1
n500-k5 | 1.3 | 1.1 | 0.8 | 1.0 | 1.7 | – | 6.0 | 3,088.7 | 40.0 | 0.1
n500–k10 | 3.4 | 3.6 | 0.6 | 1.0 | 1.7 | 4.3 | 4.4 | 2,884.1 | 45.9 | 0.1
n500-k20 | 14.8 | 14.1 | 1.3 | 1.5 | 2.5 | 3.0 | 6.3 | 3,003.3 | 79.4 | 0.1
n500-k50 | 17.9 | 6.6 | 0.8 | 1.0 | 1.2 | 2.9 | 4.6 | 2,765.2 | 157.5 | 0.2
n500-k100 | 39.7 | 3.5 | 0.8 | 1.0 | 1.4 | 19.6 | 3.6 | 2,892.1 | 306.4 | 0.2
n1000-k2 | 0.3 | 0.5 | 0.4 | 0.5 | 0.4 | 201.5 | 24.6 | 3,649.8 | 2,158.6 | 0.2
n1000-k5 | 1.3 | 1.3 | 0.9 | 0.8 | 1.3 | 28.9 | 25.8 | 3,623.0 | 1,160.5 | 0.1
n1000-k10 | 8.7 | 8.4 | 0.9 | 1.5 | 3.2 | – | 27.6 | 3,629.8 | 299.7 | 0.2
n1000-k20 | 67.9 | 66.2 | 2.7 | 4.4 | 7.2 | – | 27.6 | 3,638.4 | 270.8 | 0.1
n1000-k50 | 144.7 | 139.8 | 2.4 | 3.1 | 4.6 | 7.7 | 27.5 | 3,645.3 | 381.8 | 0.4
n1000-k100 | 212.4 | 59.5 | 1.9 | 1.9 | 2.9 | 39.0 | 31.4 | 3,628.5 | 708.9 | 0.2
n2000-k2 | 0.7 | 0.4 | 0.5 | 0.5 | 0.3 | 3,742.6 | 238.8 | 3,701.4 | 35.8 | 0.3
n2000-k5 | 0.9 | 0.9 | 0.6 | 0.5 | 0.9 | 870.3 | 232.5 | 3,755.0 | 3,434.3 | 0.1
n2000-k10 | 9.7 | 8.8 | 1.1 | 1.4 | 3.1 | – | 218.2 | 3,656.9 | 3,792.7 | 0.3
n2000-k20 | 298.7 | 293.9 | 2.9 | 4.0 | 11.2 | – | 218.8 | 3,639.1 | 3,547.9 | 0.4
n2000-k50 | 596.2 | 591.1 | 6.1 | 5.8 | 13.3 | 35.2 | 222.8 | 3,661.9 | 1,238.0 | 0.3
n2000-k100 | 1,114.9 | 1,133.9 | 4.7 | 4.9 | 7.9 | 157.9 | 219.8 | 3,651.1 | 1,916.3 | 0.5
n5000-k2 | 1.5 | 1.3 | 0.8 | 0.9 | 1.0 | – | 2,832.7 | 3,763.4 | – | 0.4
n5000-k5 | 1.1 | 1.2 | 0.9 | 0.9 | 1.0 | – | 2,854.0 | 3,877.6 | – | 0.3
n5000-k10 | 5.1 | 4.9 | 1.1 | 1.3 | 1.9 | – | 2,682.4 | 3,888.9 | – | 0.4
n5000-k20 | 219.2 | 212.9 | 2.6 | 4.5 | 13.7 | – | 2,619.7 | 3,886.3 | – | 0.5
n5000-k50 | 3,188.1 | 3,159.7 | 11.4 | 20.7 | 61.8 | – | 2,663.6 | 4,056.7 | 4,121.8 | 0.5
n5000-k100 | 3,668.6 | 3,680.5 | 17.5 | 20.4 | 51.5 | 417.0 | 2,598.4 | 3,995.0 | 3,705.7 | 0.7
Sum | 9,617.4 | 9,394.7 | 63.9 | 84.0 | 196.5 |  41,537.8∗ | 17,795.1 | 85,351.6 |  41,999.4∗ | 6.8

∗Nan values (–) are replaced with 3,600 before computing the sum.

Table 38: Average running times (in seconds) of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC) for
the constraint sets of size 10% CS. The lowest values are stated in bold. The
column KMEANS reports the average running time of the unconstrained k-means
algorithm. The hyphen indicates that the respective algorithm returned no
solution within the time limit of 3,600 seconds.

| 15% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | CSC | DILS | LCC | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
n500-k2 | 0.5 | 0.3 | 0.4 | 0.5 | 0.4 | 27.1 | 2.9 | 3,616.4 | 8.7 | 0.1
n500-k5 | 0.8 | 0.8 | 0.5 | 0.5 | 0.6 | 4.3 | 3.1 | 3,623.7 | 256.4 | 0.1
n500–k10 | 5.0 | 5.6 | 0.8 | 1.2 | 2.0 | – | 2.8 | 3,557.5 | 95.7 | 0.3
n500-k20 | 27.6 | 28.5 | 1.5 | 1.6 | 3.2 | 9.1 | 3.5 | 3,549.5 | 119.9 | 0.1
n500-k50 | 50.7 | 51.8 | 1.2 | 1.5 | 2.1 | 9.3 | 4.1 | 3,530.5 | 220.3 | 0.2
n500-k100 | 94.4 | 37.3 | 1.2 | 1.2 | 1.7 | 10.2 | 3.5 | 3,529.4 | 390.7 | 0.2
n1000-k2 | 0.6 | 0.5 | 0.4 | 0.5 | 0.5 | 538.4 | 26.3 | 3,651.7 | – | 0.2
n1000-k5 | 0.8 | 0.6 | 0.6 | 0.6 | 0.7 | 125.4 | 23.0 | 3,648.1 | 1,564.4 | 0.1
n1000-k10 | 3.8 | 3.7 | 0.7 | 0.8 | 1.3 | 19.7 | 26.1 | 3,640.2 | 3,082.7 | 0.2
n1000-k20 | 90.2 | 90.8 | 1.8 | 2.4 | 5.5 | – | 27.9 | 3,631.4 | 1,068.1 | 0.3
n1000-k50 | 317.1 | 314.8 | 2.3 | 2.8 | 6.5 | 37.0 | 26.0 | 3,617.4 | 593.4 | 0.1
n1000-k100 | 434.5 | 432.4 | 2.0 | 2.2 | 3.6 | 40.8 | 27.6 | 3,638.6 | 993.7 | 0.2
n2000-k2 | 0.8 | 0.9 | 0.4 | 0.6 | 0.7 | – | 236.3 | 3,720.4 | – | 0.4
n2000-k5 | 0.9 | 0.7 | 0.7 | 0.6 | 0.6 | 2,432.7 | 234.7 | 3,713.4 | 515.0 | 0.3
n2000-k10 | 2.9 | 2.8 | 0.6 | 0.8 | 1.3 | 561.9 | 222.1 | 3,732.1 | – | 0.5
n2000-k20 | 51.6 | 51.8 | 1.6 | 1.9 | 3.9 | 116.6 | 232.1 | 3,715.0 | 4,564.0 | 0.4
n2000-k50 | 783.1 | 787.6 | 4.1 | 6.0 | 15.3 | – | 219.4 | 3,711.7 | 3,621.9 | 0.6
n2000-k100 | 1,517.3 | 1,523.4 | 6.0 | 7.7 | 14.7 | 161.0 | 222.5 | 3,804.0 | 3,621.1 | 0.4
n5000-k2 | 1.8 | 1.9 | 1.5 | 1.5 | 1.8 | – | 2,930.6 | 3,888.4 | – | 0.3
n5000-k5 | 1.8 | 1.7 | 1.5 | 1.6 | 1.2 | – | 2,927.7 | 4,376.8 | – | 0.3
n5000-k10 | 1.6 | 1.5 | 1.2 | 1.3 | 1.5 | – | 2,833.4 | 4,394.7 | – | 0.3
n5000-k20 | 10.7 | 11.3 | 1.7 | 2.0 | 2.8 | 6,542.6 | 2,671.3 | 4,293.2 | – | 0.3
n5000-k50 | 1,820.6 | 1,828.7 | 3.8 | 9.6 | 170.7 | – | 2,656.8 | 4,159.0 | – | 0.5
n5000-k100 | 3,669.2 | 3,682.6 | 23.7 | 69.1 | 299.8 | – | 2,646.7 | 4,268.2 | 4,494.3 | 0.7
Sum | 8,888.4 | 8,862.0 | 60.2 | 118.6 | 542.3 |  43,036.1∗ | 18,210.3 | 91,011.3 |  54,010.3∗ | 7.1

∗Nan values (–) are replaced with 3,600 before computing the sum.

Table 39: Average running times (in seconds) of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC) for
the constraint sets of size 15% CS. The lowest values are stated in bold. The
column KMEANS reports the average running time of the unconstrained k-means
algorithm. The hyphen indicates that the respective algorithm returned no
solution within the time limit of 3,600 seconds.

| 20% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | CSC | DILS | LCC | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
n500-k2 | 0.4 | 0.7 | 0.4 | 0.4 | 0.4 | 54.5 | 3.5 | 3,638.6 | 6.2 | 0.1
n500-k5 | 0.6 | 0.6 | 0.4 | 0.5 | 0.5 | 12.4 | 3.5 | 3,621.5 | 1,076.1 | 0.1
n500–k10 | 2.2 | 2.1 | 0.6 | 0.8 | 1.1 | 7.3 | 2.8 | 3,613.8 | 1,239.7 | 0.1
n500-k20 | 21.3 | 23.9 | 0.9 | 1.2 | 2.4 | – | 4.4 | 3,622.3 | 303.5 | 0.1
n500-k50 | 103.0 | 105.6 | 1.5 | 1.8 | 2.3 | 13.1 | 4.6 | 3,615.3 | 325.3 | 0.1
n500-k100 | 150.1 | 150.2 | 1.1 | 1.3 | 2.0 | 40.3 | 3.2 | 3,619.9 | 461.7 | 0.2
n1000-k2 | 0.6 | 0.8 | 0.6 | 0.5 | 0.5 | 956.0 | 27.6 | 3,691.6 | – | 0.2
n1000-k5 | 0.6 | 0.5 | 0.4 | 0.5 | 0.4 | 252.6 | 25.4 | 3,696.6 | 44.8 | 0.2
n1000-k10 | 1.5 | 1.5 | 0.6 | 0.7 | 0.9 | 55.7 | 24.4 | 3,659.6 | 2,649.5 | 0.1
n1000-k20 | 43.4 | 42.4 | 1.0 | 1.7 | 3.2 | – | 24.2 | 3,646.8 | 3,670.0 | 0.2
n1000-k50 | 859.2 | 882.2 | 2.6 | 3.2 | 5.9 | – | 27.1 | 3,671.4 | 1,929.3 | 0.3
n1000-k100 | 1,250.3 | 1,257.3 | 2.1 | 3.1 | 4.1 | 80.2 | 28.4 | 3,655.6 | 1,585.6 | 0.5
n2000-k2 | 0.9 | 1.0 | 0.7 | 0.8 | 0.8 | – | 264.8 | 3,941.0 | – | 0.3
n2000-k5 | 0.8 | 0.9 | 0.7 | 0.7 | 0.7 | 4,395.5 | 260.7 | 3,877.4 | – | 0.4
n2000-k10 | 0.9 | 1.1 | 0.6 | 0.7 | 0.7 | 1,207.8 | 252.8 | 3,839.2 | 3,073.3 | 0.3
n2000-k20 | 10.7 | 11.9 | 1.0 | 1.1 | 2.2 | 288.6 | 250.9 | 3,768.9 | 4,291.7 | 0.3
n2000-k50 | 561.2 | 574.9 | 2.9 | 9.3 | 37.8 | – | 255.3 | 3,715.4 | 3,875.9 | 0.3
n2000-k100 | 3,750.8 | 3,802.3 | 6.3 | 7.8 | 17.3 | 168.7 | 248.8 | 3,696.2 | 3,666.4 | 0.6
n5000-k2 | 3.0 | 2.7 | 2.3 | 2.6 | 2.9 | – | 2,981.8 | 5,503.9 | – | 0.2
n5000-k5 | 2.0 | 2.3 | 2.0 | 1.9 | 2.1 | – | 2,939.3 | 4,871.0 | – | 0.2
n5000-k10 | 2.2 | 2.1 | 1.8 | 2.0 | 2.1 | – | 2,926.3 | 4,733.6 | – | 0.3
n5000-k20 | 2.8 | 2.9 | 1.9 | 1.8 | 2.2 | – | 2,752.5 | 4,511.0 | – | 0.3
n5000-k50 | 390.3 | 396.3 | 3.0 | 4.6 | 37.3 | 1,924.0 | 2,750.3 | 4,570.2 | – | 0.4
n5000-k100 | 3,905.5 | 3,908.7 | 9.1 | 47.8 | 333.6 | – | 2,649.0 | 4,514.9 | – | 0.5
Sum | 11,064.1 | 11,175.0 | 44.3 | 96.7 | 463.4 |  45,456.7∗ | 18,711.7 | 95,295.8 |  60,599.0∗ | 6.2

∗Nan values (–) are replaced with 3,600 before computing the sum.

Table 40: Average running times (in seconds) of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC) for
the constraint sets of size 20% CS. The lowest values are stated in bold. The
column KMEANS reports the average running time of the unconstrained k-means
algorithm. The hyphen indicates that the respective algorithm returned no
solution within the time limit of 3,600 seconds.

| 0% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | LCC | CSC | DILS | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
Banana | 0.019 | 0.019 | 0.019 | 0.019 | 0.019 | 0.018 | – | 0.030 | 0.008 | 0.017
Letter | 0.149 | 0.149 | 0.149 | 0.149 | 0.149 | 0.156 | – | – | 0.000 | 0.149
Shuttle | 0.193 | 0.193 | 0.193 | 0.193 | 0.193 | 0.429 | – | – | – | 0.411
Cifar 10 | 0.040 | 0.039 | 0.039 | 0.040 | 0.040 | – | – | – | – | 0.040
Cifar 100 | 0.021 | 0.021 | 0.021 | 0.021 | 0.021 | – | – | – | – | 0.021
Mnist | 0.306 | 0.304 | 0.304 | 0.306 | 0.306 | 0.193 | – | – | – | 0.312
Mean | 0.121 | 0.121 | 0.121 | 0.121 | 0.121 | 0.133∗ |  0.000∗ |  0.005∗ |  0.001∗ | 0.159

∗Nan values (–) are replaced with 0 before computing the mean.

Table 41: Average Adjusted Rand Index (ARI) values of five versions of the
PCCC algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS,
LCC) obtained with constraint sets of size 0% CS. Higher values indicate more
overlap with the ground truth assignment. The highest values are stated in
bold. The column KMEANS reports the average ARI values that were obtained with
the unconstrained k-means algorithm. The hyphen indicates that the respective
algorithm returned no solution within the time limit of 3,600 seconds. We
noticed that the LCC algorithm stops with a runtime error when the constraint
set is empty. This is why the LCC algorithm did not return any solutions for
the constraint sets of size 0% CS. The different PCCC versions sometimes
devise slightly different assignments for the same instance. This is because
the Gurobi solver terminates when the relative MIP optimality gap is less than
0.0001. For some instances the different PCCC versions satisfy this stopping
criterion with slightly different assignments. The differences between the
results of the PCCC versions and the results of the COPKM and the KMEANS
algorithms can be explained as follows. The COPKM algorithm uses a different
implementation of the kmeans++ algorithm, and the PCCC versions use the
Euclidean distance for parameter $d_{il}$ and not the squared Euclidean
distance which can lead to different assignments for some instances.

| 0.5% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | LCC | CSC | DILS | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
Banana | 0.018 | 0.018 | 0.018 | 0.018 | 0.018 | – | 0.006 | 0.000 | 0.003 | 0.017
Letter | 0.155 | 0.155 | 0.154 | 0.155 | 0.155 | 0.156 | 0.148 | – | 0.000 | 0.149
Shuttle | 0.502 | 0.502 | 0.503 | 0.501 | 0.502 | – | 0.312 | – | – | 0.411
Cifar 10 | 0.044 | 0.044 | 0.044 | 0.044 | 0.044 | – | – | – | – | 0.040
Cifar 100 | 0.021 | 0.022 | 0.022 | 0.022 | 0.022 | – | – | – | – | 0.021
Mnist | 0.391 | 0.391 | 0.387 | 0.391 | 0.391 | 0.217 | – | – | – | 0.312
Mean | 0.188 | 0.188 | 0.188 | 0.189 | 0.189 |  0.062∗ |  0.078∗ |  0.000∗ |  0.000∗ | 0.159

∗Nan values (–) are replaced with 0 before computing the mean.

Table 42: Average Adjusted Rand Index (ARI) values of five versions of the
PCCC algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS,
LCC) obtained with constraint sets of size 0.5% CS. Higher values indicate
more overlap with the ground truth assignment. The highest values are stated
in bold. The column KMEANS reports the average ARI values that were obtained
with the unconstrained k-means algorithm. The hyphen indicates that the
respective algorithm returned no solution within the time limit of 3,600
seconds.

| 1% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | LCC | CSC | DILS | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
Banana | 0.014 | 0.014 | 0.013 | 0.013 | 0.013 | – | 0.011 | -0.000 | 0.004 | 0.017
Letter | 0.150 | 0.150 | 0.150 | 0.151 | 0.150 | 0.154 | 0.162 | – | 0.000 | 0.149
Shuttle | 0.975 | 0.975 | 0.974 | 0.974 | 0.975 | – | – | – | – | 0.411
Cifar 10 | 0.022 | 0.022 | 0.060 | 0.047 | 0.038 | – | – | – | – | 0.040
Cifar 100 | 0.000 | 0.014 | 0.021 | 0.021 | 0.021 | – | – | – | – | 0.021
Mnist | 0.119 | 0.119 | 0.594 | 0.374 | 0.203 | – | – | – | – | 0.312
Mean | 0.213 | 0.216 | 0.302 | 0.263 | 0.233 |  0.026∗ |  0.029∗ |  -0.000∗ |  0.001∗ | 0.159

∗Nan values (–) are replaced with 0 before computing the mean.

Table 43: Average Adjusted Rand Index (ARI) values of five versions of the
PCCC algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS,
LCC) obtained with constraint sets 1%. Higher values indicate more overlap
with the ground truth assignment. The highest values are stated in bold. The
column KMEANS reports the average ARI values that were obtained with the
unconstrained k-means algorithm. The hyphen indicates that the respective
algorithm returned no solution within the time limit of 3,600 seconds.

| 5% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | LCC | CSC | DILS | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
Banana | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | – | – | 0.996 | 0.100 | 0.017
Letter | 0.651 | 0.651 | 0.588 | 0.658 | 0.667 | – | – | – | 0.000 | 0.149
Shuttle | 1.000 | 1.000 | 0.985 | 1.000 | 1.000 | – | – | – | – | 0.411
Cifar 10 | 1.000 | 1.000 | 0.570 | 0.570 | 0.672 | – | – | – | – | 0.040
Cifar 100 | – | – | 0.303 | 0.225 | 0.229 | – | – | – | – | 0.021
Mnist | 1.000 | 1.000 | 0.745 | 0.749 | 0.749 | – | – | – | – | 0.312
Mean | 0.775∗ | 0.775∗ | 0.699 | 0.701 | 0.719 |  0.000∗ |  0.000∗ |  0.166∗ |  0.017∗ | 0.159

∗Nan values (–) are replaced with 0 before computing the mean.

Table 44: Average Adjusted Rand Index (ARI) values of five versions of the
PCCC algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS,
LCC) obtained with constraint sets of size 5% CS. Higher values indicate more
overlap with the ground truth assignment. The highest values are stated in
bold. The column KMEANS reports the average ARI values that were obtained with
the unconstrained k-means algorithm. The hyphen indicates that the respective
algorithm returned no solution within the time limit of 3,600 seconds.

| 0% CS |  |
---|---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | LCC | CSC | DILS | KMEANS | GT
Dataset |  |  |  |  |  |  |  |  |  |  |
Banana | 0.389 | 0.389 | 0.389 | 0.389 | 0.389 | 0.389 | – | 0.388 | 0.185 | 0.389 | 0.032
Letter | 0.145 | 0.145 | 0.145 | 0.145 | 0.145 | 0.141 | – | – | -0.020 | 0.145 | 0.010
Shuttle | 0.356 | 0.356 | 0.356 | 0.356 | 0.356 | 0.459 | – | – | – | 0.463 | 0.300
Cifar 10 | 0.051 | 0.048 | 0.048 | 0.051 | 0.051 | – | – | – | – | 0.051 | -0.053
Cifar 100 | 0.015 | 0.015 | 0.015 | 0.015 | 0.016 | – | – | – | – | 0.015 | -0.114
Mnist | 0.004 | 0.003 | 0.003 | 0.004 | 0.004 | 0.012 | – | – | – | 0.007 | -0.043
Mean | 0.160 | 0.159 | 0.159 | 0.160 | 0.160 |  -0.167∗ |  -1.000∗ |  -0.769∗ |  -0.639∗ | 0.178 | 0.022

∗Nan values (–) are replaced with -1 before computing the mean.

Table 45: Average Silhouette coefficients of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC)
obtained with constraint sets of size 0% CS. Higher values indicate better
separated clusters. The highest values are stated in bold. The column KMEANS
reports the average Silhouette coefficients that were obtained with the
unconstrained k-means algorithm. The column GT reports the Silhouette
coefficients of the ground truth assignment. The hyphen indicates that the
respective algorithm returned no solution within the time limit of 3,600
seconds. We noticed that the LCC algorithm stops with a runtime error when the
constraint set is empty. This is why the LCC algorithm did not return any
solutions for the constraint sets of size 0% CS. The different PCCC versions
sometimes devise slightly different assignments for the same instance. This is
because the Gurobi solver terminates when the relative MIP optimality gap is
less than 0.0001. For some instances the different PCCC versions satisfy this
stopping criterion with slightly different assignments. The differences
between the results of the PCCC versions and the results of the COPKM and the
KMEANS algorithms can be explained as follows. The COPKM algorithm uses a
different implementation of the kmeans++ algorithm, and the PCCC versions use
the Euclidean distance for parameter $d_{il}$ and not the squared Euclidean
distance which can lead to different assignments for some instances.

| 0.5% CS |  |
---|---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | LCC | CSC | DILS | KMEANS | GT
Dataset |  |  |  |  |  |  |  |  |  |  |
Banana | 0.353 | 0.353 | 0.358 | 0.358 | 0.358 | – | 0.347 | 0.284 | 0.143 | 0.389 | 0.032
Letter | 0.134 | 0.134 | 0.135 | 0.135 | 0.134 | 0.134 | 0.117 | – | -0.020 | 0.145 | 0.010
Shuttle | 0.145 | 0.145 | 0.145 | 0.145 | 0.145 | – | 0.005 | – | – | 0.463 | 0.300
Cifar 10 | 0.030 | 0.030 | 0.030 | 0.030 | 0.030 | – | – | – | – | 0.051 | -0.053
Cifar 100 | 0.012 | 0.014 | 0.014 | 0.014 | 0.014 | – | – | – | – | 0.015 | -0.114
Mnist | -0.014 | -0.014 | -0.015 | -0.014 | -0.014 | -0.018 | – | – | – | 0.007 | -0.043
Mean | 0.110 | 0.111 | 0.111 | 0.111 | 0.111 |  -0.647∗ |  -0.422∗ |  -0.786∗ |  -0.646∗ | 0.178 | 0.022

∗Nan values (–) are replaced with -1 before computing the mean.

Table 46: Average Silhouette coefficients of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC)
obtained with constraint sets of size 0.5% CS. Higher values indicate better
separated clusters. The highest values are stated in bold. The column KMEANS
reports the average Silhouette coefficients that were obtained with the
unconstrained k-means algorithm. The column GT reports the Silhouette
coefficients of the ground truth assignment. The hyphen indicates that the
respective algorithm returned no solution within the time limit of 3,600
seconds.

| 1% CS |  |
---|---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | LCC | CSC | DILS | KMEANS | GT
Dataset |  |  |  |  |  |  |  |  |  |  |
Banana | 0.261 | 0.261 | 0.280 | 0.280 | 0.280 | – | 0.261 | -0.118 | 0.103 | 0.389 | 0.032
Letter | 0.113 | 0.113 | 0.113 | 0.114 | 0.113 | 0.111 | 0.110 | – | -0.020 | 0.145 | 0.010
Shuttle | 0.317 | 0.317 | 0.320 | 0.318 | 0.317 | – | – | – | – | 0.463 | 0.300
Cifar 10 | -0.029 | -0.029 | -0.010 | -0.010 | -0.015 | – | – | – | – | 0.051 | -0.053
Cifar 100 | -0.021 | -0.058 | 0.008 | 0.009 | 0.009 | – | – | – | – | 0.015 | -0.114
Mnist | -0.040 | -0.040 | -0.039 | -0.048 | -0.048 | – | – | – | – | 0.007 | -0.043
Mean | 0.100 | 0.094 | 0.112 | 0.110 | 0.109 |  -0.815∗ |  -0.605∗ |  -0.853∗ |  -0.653∗ | 0.178 | 0.022

∗Nan values (–) are replaced with -1 before computing the mean.

Table 47: Average Silhouette coefficients of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC)
obtained with constraint sets of size 1% CS. Higher values indicate better
separated clusters. The highest values are stated in bold. The column KMEANS
reports the average Silhouette coefficients that were obtained with the
unconstrained k-means algorithm. The column GT reports the Silhouette
coefficients of the ground truth assignment. The hyphen indicates that the
respective algorithm returned no solution within the time limit of 3,600
seconds.

| 5% CS |  |
---|---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | LCC | CSC | DILS | KMEANS | GT
Dataset |  |  |  |  |  |  |  |  |  |  |
Banana | 0.032 | 0.032 | 0.032 | 0.032 | 0.032 | – | – | 0.033 | 0.004 | 0.389 | 0.032
Letter | -0.027 | -0.027 | -0.049 | -0.033 | -0.033 | – | – | – | -0.017 | 0.145 | 0.010
Shuttle | 0.309 | 0.309 | 0.350 | 0.318 | 0.309 | – | – | – | – | 0.463 | 0.300
Cifar 10 | -0.053 | -0.053 | -0.203 | -0.203 | -0.145 | – | – | – | – | 0.051 | -0.053
Cifar 100 | – | – | -0.127 | -0.136 | -0.135 | – | – | – | – | 0.015 | -0.114
Mnist | -0.043 | -0.043 | -0.116 | -0.113 | -0.116 | – | – | – | – | 0.007 | -0.043
Mean |  -0.130∗ |  -0.130∗ | -0.019 | -0.022 | -0.015 |  -1.000∗ |  -1.000∗ |  -0.828∗ |  -0.669∗ | 0.178 | 0.022

∗Nan values (–) are replaced with -1 before computing the mean.

Table 48: Average Silhouette coefficients of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC)
obtained with constraint sets of size 5% CS. Higher values indicate better
separated clusters. The highest values are stated in bold. The column KMEANS
reports the average Silhouette coefficients that were obtained with the
unconstrained k-means algorithm. The column GT reports the Silhouette
coefficients of the ground truth assignment. The hyphen indicates that the
respective algorithm returned no solution within the time limit of 3,600
seconds.

| 0% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | LCC | CSC | DILS | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
Banana | 6.8 | 6.6 | 6.7 | 6.5 | 6.4 | 1.0 | – | 5,208.4 | 3,849.2 | 0.1
Letter | 684.8 | 74.3 | 74.1 | 111.0 | 150.3 | 1,007.8 | – | – | 4,450.1 | 0.5
Shuttle | 41.6 | 18.4 | 18.3 | 24.3 | 31.7 | 227.7 | – | – | – | 0.3
Cifar 10 | 1,956.3 | 380.8 | 375.6 | 1,267.4 | 1,478.0 | – | – | – | – | 18.0
Cifar 100 | 3,658.8 | 3,547.0 | 3,546.9 | 3,612.4 | 3,611.2 | – | – | – | – | 84.5
Mnist | 732.6 | 197.5 | 199.1 | 372.9 | 465.5 | 3,655.5 | – | – | – | 4.2
Sum | 7,080.9 | 4,224.6 | 4,220.9 | 5,394.6 | 5,743.2 |  12,092.0∗ |  21,600.0∗ |  23,208.4∗ |  22,699.4∗ | 107.6

∗Nan values (–) are replaced with 3,600 before computing the sum.

Table 49: Average running times (in seconds) of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC) for
the constraint sets of size 0% CS. The lowest values are stated in bold. The
column KMEANS reports the average running time of the unconstrained k-means
algorithm. The hyphen indicates that the respective algorithm returned no
solution within the time limit of 3,600 seconds. We noticed that the LCC
algorithm stops with a runtime error when the constraint set is empty. This is
why the LCC algorithm did not return any solutions for the constraint sets of
size 0% CS.

| 0.5% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | LCC | CSC | DILS | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
Banana | 3.5 | 3.6 | 4.1 | 4.2 | 4.1 | – | 94.1 | 4,415.0 | 3,622.2 | 0.1
Letter | 908.5 | 190.1 | 70.9 | 103.6 | 160.8 | 846.9 | 3,642.4 | – | 4,459.9 | 0.5
Shuttle | 148.5 | 146.7 | 25.8 | 31.9 | 50.2 | – | 4,926.2 | – | – | 0.3
Cifar 10 | 1,756.1 | 1,712.5 | 382.5 | 587.6 | 1,057.1 | – | – | – | – | 18.5
Cifar 100 | 3,810.7 | 3,631.2 | 3,576.8 | 3,624.1 | 3,612.5 | – | – | – | – | 82.3
Mnist | 1,099.9 | 1,078.4 | 241.9 | 321.9 | 535.5 | 3,884.6 | – | – | – | 4.3
Sum | 7,727.0 | 6,762.5 | 4,302.1 | 4,673.2 | 5,420.2 |  19,131.5∗ |  19,462.7∗ |  22,415.0∗ |  22,482.1∗ | 106.1

∗Nan values (–) are replaced with 3,600 before computing the sum.

Table 50: Average running times (in seconds) of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC) for
the constraint sets of size 0.5% CS. The lowest values are stated in bold. The
column KMEANS reports the average running time of the unconstrained k-means
algorithm. The hyphen indicates that the respective algorithm returned no
solution within the time limit of 3,600 seconds.

| 1% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | LCC | CSC | DILS | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
Banana | 6.7 | 6.6 | 7.6 | 7.5 | 7.4 | – | 114.5 | 3,774.8 | 3,629.6 | 0.1
Letter | 2,038.9 | 1,051.5 | 115.6 | 166.6 | 133.4 | 841.7 | 3,785.3 | – | 4,568.9 | 0.5
Shuttle | 43.8 | 43.3 | 10.0 | 12.3 | 19.7 | – | – | – | – | 0.4
Cifar 10 | 3,935.5 | 3,957.2 | 3,085.1 | 3,742.0 | 3,803.6 | – | – | – | – | 16.7
Cifar 100 | 3,820.8 | 3,838.7 | 3,575.2 | 1,837.6 | 3,628.8 | – | – | – | – | 87.1
Mnist | 3,785.2 | 3,775.2 | 3,342.5 | 3,728.4 | 3,666.3 | – | – | – | – | 4.3
Sum | 13,630.9 | 12,672.4 | 10,136.0 | 9,494.4 | 11,259.2 |  18,841.7∗ |  18,299.8∗ |  21,774.8∗ |  22,598.5∗ | 109.0

∗Nan values (–) are replaced with 3,600 before computing the sum.

Table 51: Average running times (in seconds) of five versions of the PCCC
algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC) for
the constraint sets of size 1% CS. The lowest values are stated in bold. The
column KMEANS reports the average running time of the unconstrained k-means
algorithm. The hyphen indicates that the respective algorithm returned no
solution within the time limit of 3,600 seconds.

| 5% CS |
---|---|---
| PCCC | PCCC-N2 | PCCC-N2-S | PCCC-N3-S | PCCC-N5-S | COPKM | LCC | CSC | DILS | KMEANS
Dataset |  |  |  |  |  |  |  |  |  |
Banana | 0.4 | 0.4 | 0.4 | 0.4 | 0.4 | – | – | 4,386.9 | 4,283.3 | 0.1
Letter | 1,820.1 | 1,813.6 | 229.5 | 2,365.4 | 2,874.9 | – | – | – | 4,109.1 | 0.5
Shuttle | 21.2 | 21.4 | 21.0 | 21.4 | 22.4 | – | – | – | – | 0.3
Cifar 10 | 18.1 | 18.1 | 21.8 | 22.3 | 51.6 | – | – | – | – | 17.5
Cifar 100 | – | – | 3,759.6 | 3,631.8 | 3,700.6 | – | – | – | – | 85.2
Mnist | 18.2 | 18.1 | 20.7 | 21.2 | 22.1 | – | – | – | – | 4.3
Sum |  5,477.9∗ |  5,471.6∗ | 4,053.1 | 6,062.4 | 6,672.0 |  21,600.0∗ |  21,600.0∗ |  22,386.9∗ |  22,792.4∗ | 108.0

∗Nan values (–) are replaced with 3,600 before computing the sum.

Table 52: Average running times (in seconds) of five versions of the PCCC algorithm and the four state-of-the-art algorithms (COPKM, CSC, DILS, LCC) for the constraint sets of size 5% CS. The lowest values are stated in bold. The column KMEANS reports the average running time of the unconstrained k-means algorithm. The hyphen indicates that the respective algorithm returned no solution within the time limit of 3,600 seconds.  | 5% NCS |
---|---|---
| PCCC | PCCC-S | PCCC-W | CSC-W | KMEANS
Lower bound $l$ |  |  |  |  |
0.5 | 0.44 | 0.49 | 0.53 | -0.01 | 0.53
0.6 | 0.43 | 0.49 | 0.52 | -0.01 | 0.53
0.7 | 0.44 | 0.50 | 0.52 | -0.01 | 0.53
0.8 | 0.49 | 0.57 | 0.55 | -0.01 | 0.53
0.9 | 0.49 | 0.56 | 0.56 | 0.00 | 0.53
1.0 | 0.52 | 0.58 | 0.58 | -0.01 | 0.53
Mean | 0.47 | 0.53 | 0.54 | -0.01 | 0.53
Table 53: Average Adjusted Rand Index (ARI) values of three versions of the PCCC algorithm and the state-of-the-art algorithm CSC-W obtained with noisy constraint sets of size 5% NCS. Higher values indicate more overlap with the ground truth assignment. The highest values are stated in bold. The column KMEANS reports the average ARI values that were obtained with the unconstrained k-means algorithm. | 10% NCS |
---|---|---
| PCCC | PCCC-S | PCCC-W | CSC-W | KMEANS
Lower bound $l$ |  |  |  |  |
0.5 | 0.34 | 0.48 | 0.52 | 0.01 | 0.53
0.6 | 0.43 | 0.62 | 0.60 | 0.05 | 0.53
0.7 | 0.49 | 0.67 | 0.64 | 0.13 | 0.53
0.8 | 0.55 | 0.70 | 0.69 | 0.30 | 0.53
0.9 | 0.46 | 0.71 | 0.73 | 0.32 | 0.53
1.0 | 0.78 | 0.81 | 0.81 | 0.33 | 0.53
Mean | 0.51 | 0.66 | 0.67 | 0.19 | 0.53
Table 54: Average Adjusted Rand Index (ARI) values of three versions of the
PCCC algorithm and the state-of-the-art algorithm CSC-W obtained with noisy
constraint sets of size 10% NCS. Higher values indicate more overlap with the
ground truth assignment. The highest values are stated in bold. The column
KMEANS reports the average ARI values that were obtained with the
unconstrained k-means algorithm.

| 15% NCS |
---|---|---
| PCCC | PCCC-S | PCCC-W | CSC-W | KMEANS
Lower bound $l$ |  |  |  |  |
0.5 | – | 0.42 | 0.68 | 0.31 | 0.53
0.6 | – | 0.52 | 0.68 | 0.33 | 0.53
0.7 | – | 0.70 | 0.77 | 0.32 | 0.53
0.8 | 0.54 | 0.73 | 0.77 | 0.46 | 0.53
0.9 | 0.58 | 0.84 | 0.85 | 0.55 | 0.53
1.0 | 0.92 | 0.90 | 0.90 | 0.69 | 0.53
Mean |  0.34∗ | 0.68 | 0.77 | 0.44 | 0.53

∗Nan values (–) are replaced with 0 before computing the mean.

Table 55: Average Adjusted Rand Index (ARI) values of three versions of the
PCCC algorithm and the state-of-the-art algorithm CSC-W obtained with noisy
constraint sets of size 15% NCS. Higher values indicate more overlap with the
ground truth assignment. The highest values are stated in bold. The column
KMEANS reports the average ARI values that were obtained with the
unconstrained k-means algorithm.

| 20% NCS |
---|---|---
| PCCC | PCCC-S | PCCC-W | CSC-W | KMEANS
Lower bound $l$ |  |  |  |  |
0.5 | – | 0.52 | 0.72 | 0.35 | 0.53
0.6 | – | 0.64 | 0.75 | 0.44 | 0.53
0.7 | – | 0.72 | 0.79 | 0.73 | 0.53
0.8 | – | 0.80 | 0.84 | 0.76 | 0.53
0.9 | – | 0.89 | 0.90 | 0.79 | 0.53
1.0 | 0.97 | 0.96 | 0.96 | 0.81 | 0.53
Mean |  0.16∗ | 0.76 | 0.83 | 0.65 | 0.53

∗Nan values (–) are replaced with 0 before computing the mean.

Table 56: Average Adjusted Rand Index (ARI) values of three versions of the
PCCC algorithm and the state-of-the-art algorithm CSC-W obtained with noisy
constraint sets of size 20% NCS. Higher values indicate more overlap with the
ground truth assignment. The highest values are stated in bold. The column
KMEANS reports the average ARI values that were obtained with the
unconstrained k-means algorithm.