On a local search algorithm for the capacitated max-k-cut problem

Abstract

The local search algorithm for the capacitated max-k -cut problem proposed by Gaur et al. (2008) is not guaranteed to terminate. In this note, we modify the iterative step of their algorithm to make it terminate in a finite number of steps. The modified algorithm is pseudo-polynomial, and in a special case it is strongly polynomial. Moreover, we analyze the worst case bound of the modified algorithm and give some extensions.

Keywords

• Approximation ratio
• local search
• max- -cut problem