Computational Experience with a SDP-Based Algorithm for Maximum Cut with Limited Unbalance

In the Maximum Cut with Limited Unbalance problem, we want to partition the vertices of a weighted graph into two sets of sizes differing at most by a given threshold B, so that the sum of the weights of the crossing edges is maximum. This problem has been introduced in (Galbiati and Maffioli, Theor Comput Sci 385 (2007), 78-87) where polynomial time randomized approximation algorithms are proposed and their performance guarantees are analyzed in the case of non-negative integer weights. In this article, we present extensive computational experience with these algorithms on a large number of different graphs. We then extend the analysis of these algorithms to integer weights not restricted in sign, and continue the computational testing. It turns out that the approximation ratios obtained are always substantially better than those guaranteed by the theoretical analysis. (C) 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 55(3), 247-255 2010