Noising methods for a clique partitioning problem

This paper deals with the application of noising methods to a clique partitioning problem for a weighted graph. The aim is to study different ways to add noise to the data, and to show that the choice of the noise-adding-scheme may have some impact on the performance of these methods. Among the noise-adding-schemes described here, two of them are totally new, leading to the “forgotten vertices” and to the “forgotten edges” methods. We also experimentally study a generic noising method that automatically tunes its parameters. For each noise-adding-scheme, we compare a variant which inserts descents and a variant which does not.