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

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.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.identifier.uri	http://hdl.handle.net/2003/26165
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-9020
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

Files

Now showing 1 - 1 of 1