Campus Event Calendar
Event Entry
What and Who
Evolutionary FPRAS based on dynamic programming
Anton Eremeev
Omsk Branch of Sobolev Institute of Mathematics
AG1 Mittagsseminar (own work)
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 13 October 2009
13:00
45 Minutes
E1 4
024
Saarbrücken
Abstract
In this talk, first of all some previous results will be presented, indicating that the evolutionary algorithms may be constructed to perform similar to the dynamic programming for a wide class of optimization problems. After that, some ideas from (Woeginger, 2000) will be displayed in order to define the class of DP-benevolent problems, where the dynamic programming implies existence of an FPTAS. The two approaches will be combined to show that if an NP optimization problem is DP-benevolent, then there exists an evolutionary algorithm which gives a fully polynomial randomized approximation scheme for the problem.
Contact
Frank Neumann
--email hidden
passcode not visible
logged in users only
Frank Neumann, 10/12/2009 09:55
Frank Neumann, 10/05/2009 13:09 -- Created document.
Frank Neumann, 10/05/2009 13:09 -- Created document.