Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem

Full metadata record

DC Field	Value	Language
dc.contributor.author	Horoba, Christian	de
dc.date.accessioned	2009-05-12T16:02:23Z	-
dc.date.available	2009-05-12T16:02:23Z	-
dc.date.issued	2008-12	de
dc.identifier.uri	http://hdl.handle.net/2003/26165	-
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-9020	-
dc.description.abstract	We present a natural fitness function f for the multiobjective shortest path problem, which is a fundamental multiobjective combinatorial optimization problem known to be NP-hard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem under consideration, which exemplifies how EAs are able to find good approximate solutions for hard problems.	en
dc.language.iso	en	de
dc.relation.ispartofseries	Reihe CI; 258-08	de
dc.subject.ddc	004	de
dc.title	Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem	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
25808.pdf	DNB	223.47 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