The max k-cut problem is a graph partitioning problem with applications in various fields. It involves partitioning the vertices of a graph into k disjoint sets so as to maximize the sum of the weights of edges connecting vertices belonging to different sets. However, due to its \(\mathcal {NP}\) -hard complexity, it is not possible to solve the problem quickly for large graphs. In this paper, we propose an algorithm using the greedy randomized adaptive search procedure and path relinking heuristics to solve the problem with an approximation ratio of \(\left( 1 - \frac{1}{k}\right)\) . We then introduce optimizations with a novel contributions matrix, which considerably improves the time complexity of the algorithm. Experiments show that using this method to cluster data results in it outperforming the more commonly used k-means algorithm and Ward’s method of agglomerative clustering. Furthermore, the proposed algorithm uses far less time and memory than a semidefinite programming approximation algorithm while producing solutions of similar quality.
