On the size of weights in randomized search heuristics

dc.contributor.author	Reichel, Joachim	de
dc.contributor.author	Skutella, Martin	de
dc.date.accessioned	2009-05-12T16:02:13Z
dc.date.available	2009-05-12T16:02:13Z
dc.date.issued	2008-08	de
dc.description.abstract	Runtime analyses of randomized search heuristics for combinatorial optimization problems often depend on the size of the largest weight. We consider replacing the given set of weights with smaller weights such that the behavior of the randomized search heuristic does not change. Upper bounds on the size of the new, equivalent weights allow us to obtain upper bounds on the expected runtime of such randomized search heuristics independent of the size of the actual weights. Furthermore we give lower bounds on the largest weights for worst-case instances. Finally we present some experimental results, including examples for worst-case instances.	en
dc.identifier.uri	http://hdl.handle.net/2003/26160
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-9027
dc.language.iso	en	de
dc.relation.ispartofseries	Reihe CI; 253-08	de
dc.subject	analysis of algorithms and problem complexity	en
dc.subject	evolutionary algorithms	en
dc.subject	performance	en
dc.subject	randomized search heuristics	en
dc.subject	theory of computation	en
dc.subject.ddc	004	de
dc.title	On the size of weights in randomized search heuristics	en
dc.type	Text	de
dc.type.publicationtype	report	de
dcterms.accessRights	open access

Files

Now showing 1 - 1 of 1