2026-07-28T00:22:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4967 2024-03-06T10:26:18Z ddc:004 open_access

Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451) Kratsch, Stefan Lokshtanov, Daniel Marx, Dániel Rossmanith, Peter Algorithms parameterized complexity kernels width measures exponential time hypothesis lower bounds This report documents the program and the outcomes of Dagstuhl Seminar 14451 "Optimality and tight results in parameterized complexity". Over the last two decades parameterized complexity has become one of the main tools for handling intractable problems. Recently, tools have been developed not only to classify problems, but also to make statements about how close an algorithm is to being optimal with respect to running time. The focus of this seminar is to highlight and discuss recent, relevant results within this optimality framework and discover fruitful research directions. The report contains the abstracts of the results presented at the seminar, as well as a collection of open problems stated at the seminar. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Kratsch and Daniel Lokshtanov and Dániel Marx and Peter Rossmanith 2015 Is Part Of Dagstuhl Reports, Volume 4, Issue 11 (2015) Article Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagRep.4.11.1 urn:nbn:de:0030-drops-49677 https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.11.1 eng https://creativecommons.org/licenses/by/3.0/legalcode