|Title:||A Comparison of Approximation Algorithms for the MaxCut-Problem|
|Abstract:||In 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.|
|Appears in Collections:||Sonderforschungsbereich (SFB) 531|
Files in This Item:
|ci57.pdf||DNB||298.1 kB||Adobe PDF||View/Open|
This item is protected by original copyright
All resources in the repository are protected by copyright.