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
- 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)
Contact
- Michael Gerke (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Impacts
- Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs - Lee, Euiwoong; Manurangsi, Pasin - Cornell University : arXiv.org, 2023. - 19 pp..
- Conditional lower bounds for sparse parameterized 2-CSP : A streamlined proof - Karthik C. S.; Marx, Daniel; Pilipczuk, Marcin; Souza, Ueverton S. - arXiv.org, 2023. - 18 pp..
- Conditional lower bounds for sparse parameterized 2-CSP : A streamlined proof : article in Proceedings : 2024 Symposium on Simplicity in Algorithms - Karthik C. S.; Marx, Dániel; Pilipczuk, Marcin; Souza, Uéverton - Philadelphia : SIAM, 2023. - pp. 383-395.
- On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP - Karthik C. S.; Lee, Euiwoong; Manurangsi, Pasin - Cornell University : arXiv.org, 2024. - 20 pp..
- Separating k-MEDIAN from the Supplier Version : article in International Conference on Integer Programming and Combinatorial Optimization 2024 - Anand, Aditya ; Lee, Euiwoong - Berlin : Springer, 2024. - pp. 14-27 - (Lecture notes in computer science ; 14679 : article).
Schedule
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 studied parameterized approximation as a relatively new algorithmic paradigm that combines these two popular research areas. In particular, we analyzed 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. In this seminar, we brought together researchers from both communities in order to bridge this gap by accommodating the exchange and unification of scientific knowledge.
Our first goal was to foster a transfer of techniques between the classic fields of approximation and parameterization. We discussed how recent developments in one research area can be transferred to another. Towards this, we organized five invited one-hour tutorials (one on each morning) that were delivered by leading experts from the fields and which we believe helped exchange of state-of-the-art techniques. The tutorial topics covered parameterized or polynomial time approximation algorithms for graph edit and network design problems, for clustering problems, matroid constrained maximization problems, as well as the hardness of parameterized approximation of problems arising in error correcting codes.
Our second goal was to systematically identify important research directions and concrete open problems in research areas that are relevant to parameterized approximation. Towards this, we organized a panel discussion on the first seminar day led by experts from parameterized algorithms, approximation algorithms, hardness of approximation, but also from neighboring areas such as fine-grained complexity and coding theory. A vibrant discussion ensued between the moderator, panelists, but also the other participants. Moreover, we organized two open discussion sessions, which were open to any participant to bring up a topic they would like to discuss with the other participants: This could be, for example, concrete open problems, more general research directions, or highlights. Besides several concrete open problems suggested by particpants, there were two contributions to the sessions that gave overviews over a coherent collection of open questions on hardness of parameterized approximation under Gap-ETH and beyond, as well as on the parameterized (in-)approximability of clustering problems.
Our third goal was to 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. It was therefore a particular priority for us to provide sufficient time for collaboration. Towards this, we reserved time slots for six collaboration sessions and one session for progress reports.
We thank Martin Herold for collecting the abstracts from the participants and for his assistance with creating and editing the report.
Creative Commons BY 4.0
Joachim Spoerhase, Karthik C. S., Parinya Chalermsook, and Meirav Zehavi
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.
Karthik C. S., Parinya Chalermsook, Joachim Spoerhase, and Meirav Zehavi
- Amir Abboud (Weizmann Institute - Rehovot, IL) [dblp]
- Antonios Antoniadis (University of Twente, NL) [dblp]
- Jarek Byrka (University of Wroclaw, PL) [dblp]
- Karthik C. S. (Rutgers University - New Brunswick, US) [dblp]
- Parinya Chalermsook (Aalto University, FI) [dblp]
- Vincent Cohen-Addad (Google - Paris, FR) [dblp]
- Klim Efremenko (Ben Gurion University - Beer Sheva, IL) [dblp]
- Andreas Emil Feldmann (University of Sheffield, GB) [dblp]
- Michael R. Fellows (University of Bergen, NO) [dblp]
- Ameet Gadekar (Aalto University, FI) [dblp]
- Fabrizio Grandoni (SUPSI - Lugano, CH) [dblp]
- Carla Groenland (Utrecht University, NL) [dblp]
- Venkatesan Guruswami (University of California - Berkeley, US) [dblp]
- Martin Herold (MPI für Informatik - Saarbrücken, DE)
- Lawqueen Kanesh (Indian Institute of Techology - Jodhpur, IN) [dblp]
- Matthias Kaul (TU Hamburg, DE) [dblp]
- Madhumita Kundu (University of Bergen, NO) [dblp]
- Euiwoong Lee (University of Michigan - Ann Arbor, US) [dblp]
- Jason Li (University of California - Berkeley, US) [dblp]
- Bingkai Lin (Nanjing University, CN) [dblp]
- Pasin Manurangsi (Google Thailand - Bangkok, TH) [dblp]
- Dániel Marx (CISPA - Saarbrücken, DE) [dblp]
- Pranabendu Misra (Chennai Mathematical Institute, IN) [dblp]
- Tobias Mömke (Universität Augsburg, DE) [dblp]
- Danupon Nanongkai (MPI für Informatik - Saarbrücken, DE) [dblp]
- Marcin Pilipczuk (University of Warsaw, PL) [dblp]
- Nidhi Purohit (University of Bergen, NO) [dblp]
- Rajiv Raman (University Blaise Pascal - Aubiere, FR & IIIT Delhi - New Delhi, IN) [dblp]
- Frances A. Rosamond (University of Bergen, NO) [dblp]
- Saket Saurabh (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Chris Schwiegelshohn (Aarhus University, DK) [dblp]
- Hadas Shachnai (Technion - Haifa, IL) [dblp]
- Roohani Sharma (MPI für Informatik - Saarbrücken, DE) [dblp]
- Krzysztof Sornat (SUPSI - Lugano, CH) [dblp]
- Joachim Spoerhase (University of Sheffield, 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]
Classification
- Computational Complexity
- Data Structures and Algorithms
- Discrete Mathematics
Keywords
- Combinatorial Optimization
- Approximation Algorithms
- Parameterized Complexity
- Hardness of Approximation
