A Comparison of Approximation Algorithms for the MaxCut-Problem

dc.contributor.author	Dolezal, Oliver	de
dc.contributor.author	Hofmeister, Thomas	de
dc.contributor.author	Lefmann, Hanno	de
dc.date.accessioned	2004-12-07T08:19:57Z
dc.date.available	2004-12-07T08:19:57Z
dc.date.created	1999	de
dc.date.issued	2001-10-16	de
dc.description.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.	en
dc.format.extent	305251 bytes
dc.format.extent	400909 bytes
dc.format.mimetype	application/pdf
dc.format.mimetype	application/postscript
dc.identifier.uri	http://hdl.handle.net/2003/5366
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-5013
dc.language.iso	en	de
dc.publisher	Universität Dortmund	de
dc.relation.ispartofseries	Reihe Computational Intelligence ; 57	de
dc.subject.ddc	004	de
dc.title	A Comparison of Approximation Algorithms for the MaxCut-Problem	en
dc.type	Text	de
dc.type.publicationtype	report
dcterms.accessRights	open access

Files

Now showing 1 - 2 of 2