Correlation Clustering on SBM instance n=50, k=5 (15 trials)
2.32Approximation RatioFull LP-Pivot
Evaluation Results
| Method | Links | ||
|---|---|---|---|
| Full LP-Pivotm=25, m/n^{3/2}=0.072026.02 | 2.32 | 98.1 | |
| KwikClusterm=25, m/n^{3/2}=0.072026.02 | 2.32 | 98.1 | |
| Full LP-Pivotm=50, m/n^{3/2}=0.142026.02 | 2.32 | 93 | |
| KwikClusterm=50, m/n^{3/2}=0.142026.02 | 2.32 | 93 | |
| Full LP-Pivotm=100, m/n^{3/2}=0.282026.02 | 2.32 | 73.1 | |
| KwikClusterm=100, m/n^{3/2}=0.282026.02 | 2.32 | 73.1 | |
| Full LP-Pivotm=353, m/n^{3/2}=1.002026.02 | 2.32 | 1.7 | |
| KwikClusterm=353, m/n^{3/2}=1.002026.02 | 2.32 | 1.7 | |
| Sparse-LP-Pivotm=706, m/n^{3/2}=2.002026.02 | 2.32 | 0 | |
| Full LP-Pivotm=706, m/n^{3/2}=2.002026.02 | 2.32 | 0 | |
| KwikClusterm=706, m/n^{3/2}=2.002026.02 | 2.32 | 0 | |
| Sparse-LP-Pivotm=353, m/n^{3/2}=1.002026.02 | 2.43 | 1.7 | |
| Sparse-LP-Pivotm=100, m/n^{3/2}=0.282026.02 | 7.08 | 73.1 | |
| Sparse-LP-Pivotm=50, m/n^{3/2}=0.142026.02 | 7.98 | 93 | |
| Sparse-LP-Pivotm=25, m/n^{3/2}=0.072026.02 | 8.31 | 98.1 |