Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:The Optimality Program in Parameterized Algorithms
Speaker:Daniel Marx
coming from:Hungarian Academy of Sciences
Speakers Bio:
Event Type:INF Distinguished Lecture Series
Visibility:D1, D3, D4, RG1, MMCI, D2, D5, SWS
We use this to send out email in the morning.
Level:MPI Audience
Date, Time and Location
Date:Monday, 12 November 2018
Duration:60 Minutes
Building:E1 4
Parameterized complexity analyzes the computational complexity of

NP-hard combinatorial problems in finer detail than classical
complexity: instead of expressing the running time as a univariate
function of the size $n$ of the input, one or more relevant parameters
are defined and the running time is analyzed as a function depending
on both the input size and these parameters. The goal is to obtain
algorithms whose running time depends polynomially on the input size,
but may have arbitrary (possibly exponential) dependence on the
parameters. Moreover, we would like the dependence on the parameters
to be as slowly growing as possible, to make it more likely that the
algorithm is efficient in practice for small values of the
parameters. In recent years, advances in parameterized algorithms and
complexity have given us a tight understanding of how the parameter
has to influence the running time for various problems. The talk will
survey results of this form, showing that seemingly similar NP-hard
problems can behave in very different ways if they are analyzed in the
parameterized setting.

Name(s):Kurt Mehlhorn
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Kurt Mehlhorn/AG1/MPII/DE, 11/06/2018 02:48 PM
Last modified:
Uwe Brahm/MPII/DE, 11/12/2018 07:01 AM
  • Kurt Mehlhorn, 11/07/2018 03:53 PM
  • Kurt Mehlhorn, 11/06/2018 02:49 PM
  • Kurt Mehlhorn, 11/06/2018 02:48 PM -- Created document.