Hybrid local search approximation algorithm for solving the capacitated Max-K-cut problem

摘要

In this article we propose a new hybrid local search approximation algorithm for solving the capacitated Max-k-cut problem and contrast its performance with two local search approximation algorithms. The first of which uses a swapping neighborhood search technique, whereas the second algorithm uses a vertex movement method. We analyze the behavior of the three algorithms with respect to running time complexity, number of iterations performed and the total weight sum of the cut edges. The experimental results show that our proposed hybrid algorithm outperforms its rivals at all levels.