Finding the optimal solution of the standard Min Cut with non-negative edge weights, i.e., when \(\mathbf {X}_{ij}\ge 0, \forall i,j\) , is well-studied, for which there exist several polynomial time algorithms, e.g., \(\mathcal {O}(n^4)\)  [1]} and \(\mathcal {O}(n^2 \log ^3 n)\)  [2]}.
However, finding the optimal solution of the Shifted Min Cut cost function, wherein some edge weights are negative, is NP-hard [3]}, [4]} and even is APX-hard [4]}.
Therefore, we develop a local search method which computes a local minimum of the cost function in Eq. REF . The effectiveness of such a greedy strategy is well studied for different clustering cost functions, e.g., \(K\) -means [6]}, kernel \(K\) -means [7]} and in particular several graph partitioning methods [8]}, [9]}.Consistently, with Correlation Clustering we observe a significantly better performance of the local search algorithm compared to approximation schemes such as those proposed in [3]}, [4]}. In this approach, we start with a random clustering solution and then we iteratively assign each object to the cluster that yields a maximal reduction in the cost function. We repeat this procedure until no further change of assignments is achieved during a complete round of investigation of the objects, i.e., then a local optimal solution is attained.
