New Horizons in Parameterized Complexity (Dagstuhl Seminar 19041)

Authors Fedor V. Fomin, Dániel Marx, Saket Saurabh, Meirav Zehavi and all authors of the abstracts in this report



PDF
Thumbnail PDF

File

DagRep.9.1.67.pdf
  • Filesize: 8.85 MB
  • 21 pages

Document Identifiers

Author Details

Fedor V. Fomin
Dániel Marx
Saket Saurabh
Meirav Zehavi
and all authors of the abstracts in this report

Cite AsGet BibTex

Fedor V. Fomin, Dániel Marx, Saket Saurabh, and Meirav Zehavi. New Horizons in Parameterized Complexity (Dagstuhl Seminar 19041). In Dagstuhl Reports, Volume 9, Issue 1, pp. 67-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/DagRep.9.1.67

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.
Keywords
  • Intractability
  • Parameterized Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail