Premium
Computational experience with a SDP‐based algorithm for maximum cut with limited unbalance
Author(s) -
Galbiati Giulia,
Gualandi Stefano,
Maffioli Francesco
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20369
Subject(s) - partition (number theory) , mathematics , integer (computer science) , algorithm , computational complexity theory , approximation algorithm , combinatorics , partition problem , integer programming , graph , time complexity , computer science , discrete mathematics , programming language
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. © 2010 Wiley Periodicals, Inc. NETWORKS 2010