License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagRep.9.1.67
URN: urn:nbn:de:0030-drops-105706
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10570/
Go back to Dagstuhl Reports


Fomin, Fedor V. ; Marx, Dániel ; Saurabh, Saket ; Zehavi, Meirav
Weitere Beteiligte (Hrsg. etc.): Fedor V. Fomin and Dániel Marx and Saket Saurabh and Meirav Zehavi

New Horizons in Parameterized Complexity (Dagstuhl Seminar 19041)

pdf-format:
dagrep_v009_i001_p067_19041.pdf (9 MB)


Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 19041 "New Horizons in Parameterized Complexity".

Parameterized Complexity is celebrating its 30th birthday in 2019. In these three decades, there has been tremendous progress in developing the area. The central vision of Parameterized Complexity through all these years has been to provide the algorithmic and complexity-theoretic toolkit for studying multivariate algorithmics in different disciplines and subfields of Computer Science. These tools are universal as they did not only help in the development of the core of Parameterized Complexity, but also led to its success in other subfields of Computer Science such as Approximation Algorithms, Computational Social Choice, Computational Geometry, problems solvable in P (polynomial time), to name a few.

In the last few years, we have witnessed several exciting developments of new parameterized techniques and tools in the following subfields of Computer Science and Optimization: Mathematical Programming, Computational Linear Algebra, Computational Counting, Derandomization, and Approximation Algorithms.
The main objective of the seminar was to initiate the discussion on which of the recent
domain-specific algorithms and complexity advances can become useful in other domains.

BibTeX - Entry

@Article{fomin_et_al:DR:2019:10570,
  author =	{Fedor V. Fomin and D{\'a}niel Marx and Saket Saurabh and Meirav Zehavi},
  title =	{{New Horizons in Parameterized Complexity (Dagstuhl Seminar 19041)}},
  pages =	{67--87},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{1},
  editor =	{Fedor V. Fomin and D{\'a}niel Marx and Saket Saurabh and Meirav Zehavi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10570},
  URN =		{urn:nbn:de:0030-drops-105706},
  doi =		{10.4230/DagRep.9.1.67},
  annote =	{Keywords: Intractability, Parameterized Complexity}
}

Keywords: Intractability, Parameterized Complexity
Collection: Dagstuhl Reports, Volume 9, Issue 1
Issue Date: 2019
Date of publication: 19.06.2019


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI