Approximating minimum multicuts by evolutionary multi-objective algorithms

Full metadata record

DC Field	Value	Language
dc.contributor.author	Neumann, Frank	de
dc.contributor.author	Reichel, Joachim	de
dc.date.accessioned	2009-05-12T16:02:03Z	-
dc.date.available	2009-05-12T16:02:03Z	-
dc.date.issued	2008-06	de
dc.identifier.uri	http://hdl.handle.net/2003/26156	-
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-12771	-
dc.description.abstract	It has been shown that simple evolutionary algorithms are able to solve the minimum cut problem in expected polynomial time when using a multi-objective model of the problem. In this paper, we generalize these ideas to the NP-hard minimum multicut problem. Given a set of k terminal pairs, we prove that evolutionary algorithms in combination with a multi-objective model of the problem are able to obtain a k-approximation for this problem in expected polynomial time.	en
dc.language.iso	en	de
dc.relation.ispartofseries	Reihe CI; 249-08	de
dc.subject.ddc	004	de
dc.title	Approximating minimum multicuts by evolutionary multi-objective algorithms	en
dc.type	Text	de
dc.type.publicationtype	report	de
dcterms.accessRights	open access	-
Appears in Collections:	Sonderforschungsbereich (SFB) 531

Files in This Item:

File	Description	Size	Format
24908.pdf	DNB	211.31 kB	Adobe PDF	View/Open

This item is protected by original copyright

Show simple item record

This item is protected by original copyright rightsstatements.org