Campus Event Calendar
Event Entry
What and Who
A Tight Analysis of the (1+1)-EA for the Single Source Shortest Path Problem
Christian Klein
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 30 November 2007
13:30
30 Minutes
E1 4
024
Saarbrücken
Abstract
We present a rigorous analysis of the (1+1) evolutionary algorithm for the single source shortest path problem.
We show both an upper as well as a matching lower bound on the expected optimisation time of the (1+1)-EA.
Also, using Chernoff Bounds, we are able to prove that these bounds not only hold in expectation, but also with high probability.
Contact
Christian Klein
--email hidden
passcode not visible
logged in users only
Christian Klein, 11/29/2007 23:51 -- Created document.