Dagstuhl-Seminar 23291
Parameterized Approximation: Algorithms and Hardness
( 16. Jul – 21. Jul, 2023 )
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/23291
Organisatoren
- Karthik C. S. (Rutgers University - New Brunswick, US)
- Parinya Chalermsook (Aalto University, FI)
- Joachim Spoerhase (University of Sheffield, GB)
- Meirav Zehavi (Ben Gurion University - Beer Sheva, IL)
Kontakt
- Michael Gerke (für wissenschaftliche Fragen)
- Susanne Bach-Bernhard (für administrative Fragen)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
Gemeinsame Dokumente
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Programm
- Upload (Use personal credentials as created in DOOR to log in)
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.
Creative Commons BY 4.0
Karthik C. S., Parinya Chalermsook, Joachim Spoerhase, and Meirav Zehavi
- Amir Abboud (Weizmann Institute - Rehovot, IL) [dblp]
- Akanksha Agrawal (Indian Institute of Techology Madras, IN) [dblp]
- Antonios Antoniadis (University of Twente, NL) [dblp]
- Jarek Byrka (University of Wroclaw, PL)
- Karthik C. S. (Rutgers University - New Brunswick, US)
- Parinya Chalermsook (Aalto University, FI) [dblp]
- Rajesh Hemant Chitnis (University of Birmingham, GB) [dblp]
- Vincent Cohen-Addad (Google - Paris, FR) [dblp]
- Klim Efremenko (Ben Gurion University - Beer Sheva, IL) [dblp]
- Andreas Emil Feldmann (Charles University - Prague, CZ)
- Michael R. Fellows (University of Bergen, NO) [dblp]
- Fabrizio Grandoni (SUPSI - Lugano, CH) [dblp]
- Carla Groenland (Utrecht University, NL)
- Anupam Gupta (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Venkatesan Guruswami (University of California - Berkeley, US) [dblp]
- Bundit Laekhanukit (Shanghai University of Finance and Economics, CN)
- Euiwoong Lee (University of Michigan - Ann Arbor, US) [dblp]
- Jason Li (University of California - Berkeley, US)
- Bingkai Lin (Nanjing University, CN) [dblp]
- Dániel Marx (CISPA - Saarbrücken, DE) [dblp]
- Pranabendu Misra (Chennai Mathematical Institute, IN)
- Matthias Mnich (TU Hamburg, DE) [dblp]
- Tobias Mömke (Universität Augsburg, DE)
- Marcin Pilipczuk (University of Warsaw, PL) [dblp]
- Rajiv Raman (University Blaise Pascal - Aubiere, FR & IIIT Delhi - New Delhi, IN)
- Frances A. Rosamond (University of Bergen, NO) [dblp]
- Saket Saurabh (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Hadas Shachnai (Technion - Haifa, IL) [dblp]
- Krzysztof Sornat (SUPSI - Lugano, CH) [dblp]
- José Soto San Martín (University of Chile - Santiag de Chile, CL)
- Joachim Spoerhase (University of Sheffield, GB)
- Ramanujan Sridharan (University of Warwick - Coventry, GB) [dblp]
- Vera Traub (Universität Bonn, DE) [dblp]
- Daniel Vaz (ENS - Paris, FR)
- Andreas Wiese (TU München, DE) [dblp]
- Meirav Zehavi (Ben Gurion University - Beer Sheva, IL) [dblp]
- Hang Zhou (Ecole Polytechnique - Palaiseau, FR) [dblp]
Klassifikation
- Computational Complexity
- Data Structures and Algorithms
- Discrete Mathematics
Schlagworte
- Combinatorial Optimization
- Approximation Algorithms
- Parameterized Complexity
- Hardness of Approximation
