Campus Event Calendar
Event Entry
What and Who
Connections between parameterized complexity and approximability
Michael Fellows
Max-Planck-Institut für Informatik - D1
Talk
AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS
MPI Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 30 September 2008
10:30
60 Minutes
E1 4
024
Saarbrücken
Abstract
There are many results and conjectures about connections between approximability of optimization problems and the parameterized complexity of their natural parameterized counterparts. This includes the relation between efficient PTASs and fixed-parameter tractability as well as the general impression that constant approximability is closely related to the existence of a polynomial kernelization. Michael will summarize and explain some of these results and point out new research opportunities.
Again, everybody should feel free to come.
Contact
Stefan Kratsch
--email hidden
passcode not visible
logged in users only
Stefan Kratsch, 09/24/2008 15:57
Stefan Kratsch, 09/24/2008 15:57 -- Created document.
Stefan Kratsch, 09/24/2008 15:57 -- Created document.