A Comparison of Approximation Algorithms for the MaxCut-Problem

Full metadata record

DC Field	Value	Language
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.identifier.uri	http://hdl.handle.net/2003/5366	-
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-5013	-
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.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	-
Appears in Collections:	Sonderforschungsbereich (SFB) 531

Files in This Item:

File	Description	Size	Format
ci57.pdf	DNB	298.1 kB	Adobe PDF	View/Open
ci57.ps		391.51 kB	Postscript	View/Open

This item is protected by original copyright

Show simple item record

This item is protected by original copyright rightsstatements.org