Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

On 16.6.2014 at 11:00 in S4, there is the following noon lecture:

Multivariate Algorithmics for Hard Optimization Problems

Matthias Mnich

Bonn University

Abstract

Many fundamental discrete optimization problems are intractable; that is, they cannot be solved efficiently (in polynomial time) according to classical theory. Yet, in engineering, natural sciences, social sciences, and other domains, large-scale instances of those hard problems are solved to optimality, because instances arising in practice always carry some obvious or hidden structures that can be utilized by powerful algorithms.

Our research in combinatorial algorithms and discrete optimization aims to discover all the relevant algorithmic techniques for those problem domains and prove the optimality of these techniques. The search for such results should be done by a combined exploration of the dimensions running time, quality of solution, and generality. The theory of parameterized complexity provides a framework for this exploration.

Parameterized complexity is a theory whose goal is

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

Webmaster: kamweb.mff.cuni.cz         Archive page