TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 23291

Parameterized Approximation: Algorithms and Hardness

( Jul 16 – Jul 21, 2023 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/23291

Organizers

Contact

Shared Documents


Schedule

Motivation

Parameterization and approximation are two popular approaches of coping with intractability in combinatorial optimization. They have gained substantial maturity over the last decades, leading to tight bounds for many fundamental computational problems and beautiful algorithmic techniques that show surprising interplay between algorithms and various areas of mathematics. In this Dagstuhl Seminar, we study parameterized approximation as a relatively new algorithmic paradigm that combines these two popular research areas. In particular, we analyze the solution quality (approximation ratio) as well as the running time of an algorithm in terms of a parameter that captures the “complexity” of a problem instance.

While the field has grown and yielded some promising results, our understanding of the area is rather ad-hoc compared to our knowledge in approximation or parameterized algorithms alone. The goal of this seminar is to work towards bridging this gap. We want to bring together researchers from both communities in order to accommodate the unification of scientific knowledge. (i) We aim at fostering a transfer of techniques between the classic fields of approximation and parameterization. We will discuss how recent developments in one research area can be transferred to another. The exchange of state-of-the-art techniques will be achieved through several invited tutorials that will be delivered by top experts in the two fields. (ii) We plan to systematically identify new research programs and concrete open problems in research areas that are relevant to parameterized approximation. This goal will be achieved through several panel discussions led by experts in selected areas. (iii) We will bolster the creation of new collaborations between researchers in the two communities by encouraging the participants to actively discuss the suggested directions for open problems. In particular, we will reserve time slots for research discussions dedicated for this purpose.

Copyright Karthik C. S., Parinya Chalermsook, Joachim Spoerhase, and Meirav Zehavi

Participants

Classification
  • Computational Complexity
  • Data Structures and Algorithms
  • Discrete Mathematics

Keywords
  • Combinatorial Optimization
  • Approximation Algorithms
  • Parameterized Complexity
  • Hardness of Approximation