Parameterized Approximation Algorithms Workshop (PAAW)
2022: Paris, France
A satellite workshop of ICALP 2022 taking place in Paris, France, on Monday July 4th 2022.
Two standard approaches to handle hard (typically NP-hard) optimization problems are to develop approximation and parameterized algorithms. For the former, the runtime should be polynomial in the input size, but the computed solution may deviate from the optimum. For the latter, the optimum solution should be computed, but any super-polynomial runtime should be isolated to some parameter of the input. Some problems however are hard to approximate on one hand, and on the other it is also hard to obtain parameterized algorithms for some given parameter. In this case one may still hope to obtain parameterized approximation algorithms, which combine the two paradigms, i.e. the computed solution may deviate from the optimum and the runtime should have super-polynomial dependence only in some given parameter. Recently there has been a great deal of development in proving the existence or non-existence of parameterized approximation algorithms, and the aim of this workshop is to bring together active researchers of this emerging field, so that they may share their results and insights.
A list of open problems presented during the workshop can be found here.
Tuukka Korhonen (University of Bergen)
Fast FPT 2-Approximation Algorithms for Width Parameters
I talk about algorithms to 2-approximate treewidth and branchwidth in 2^O(k) n time and rankwidth in 2^2^O(k) n^2 time. These algorithms are based on designing "refinement operations" for the corresponding decompositions and showing that these refinement operations can be efficiently implemented via dynamic programming and amortization techniques. The talk is based on papers https://arxiv.org/abs/2104.07463, and https://arxiv.org/abs/2111.03492 which is joint work with Fedor V. Fomin.
Contributed talks and schedule
09:30: René van Bevern: "Parameterized approximation approaches on real-world instances: three cases"
10:00: Ariel Kulik: "Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations"
11:00: Tuukka Korhonen (invited talk): "Fast FPT 2-Approximation Algorithms for Width Parameters"
12:00: Matthias Kaul: "Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter"
14:00: Baris Can Esmer: "Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search"
14:30: Prafullkumar Tale: "On the Parameterized Approximability of Contraction to Classes of Chordal Graphs"
15:00: Chien-Chung Huang: "Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms"
16:00: Aviad Rubinstein: "SETH vs Approximation"
16:30: open problem session
The workshop will take place as a satellite workshop of ICALP 2022 in Paris, France, on July 4th 2022.
The workshop is held in the Avogadro A room on the 2nd floor of 45 rue de Saints-Pères: https://maps.app.goo.gl/9D7b5oiiJgzohc5F8
Topics of interest
Parameterized approximation algorithms
Fine-grained complexity of approximation
Subexponential time approximation
Efficient polynomial-time approximation schemes
Submission deadline: Friday May 27th
Notification: Friday June 10th
Early registration deadline (for ICALP): Wednesday May 18th
Workshop: Monday July 4th
To participate at the workshop please register through the ICALP registration page.
Andreas Emil Feldmann (email@example.com)
Michail Lampis (firstname.lastname@example.org)
Please don't hesitate to send us emails with any question you have regarding this workshop.