Matthias Mnich's venia legendi "Multivariate Algorithmics for Hard Optimization Problems"

Klipi teostus: Mirjam Paales 19.03.2015 1852 vaatamist Arvutiteadus


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 to produce efficient algorithms for hard optimization problems using a multi-dimensional analysis of the running time. These algorithms run in time that is polynomial in the large input size, and exponential only in the structures that govern the difficulty of the problem. Our multivariate algorithms identify and harness those structures, to solve hard optimization problems efficiently in theory and practice.