Dolezal, OliverHofmeister, ThomasLefmann, Hanno2004-12-072004-12-0719992001-10-16http://hdl.handle.net/2003/536610.17877/DE290R-5013In this paper we compare, from a practical point of view, approximation algorithms for the problem MaxCut . For this problem, we are given an undirected graph G = (V;E) with vertex set V and edge set E, and we are looking for a partition V = V1 [ V2 with V1 \ V2 = 0 of the vertex set which maximizes the number of edges e 2 E which have one endpoint in V1 and the other in V2 . The investigated algorithms include semidefinite programming, a random strategy, genetic algorithms, two combinatorial algorithms and a divide-and-conquer strategy.enUniversität DortmundReihe Computational Intelligence ; 57004report