Parameterized Approximation Algorithms Workshop (PAAW)
2018: Prague, Czechia
A satellite workshop of ICALP 2018 taking place in Prague, Czechia, on Monday July 9th 2018.
Scope
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.
Abstracts
Booklet now available as PDF.
Schedule of contributed talks
09:00 – 09:30: Parinya Chalermsook: From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
09:30 – 10:00: Bingkai Lin: FPT-Inapproximability of Minimum Codeword Problem over Large Fields
10:00 – 10:30: Bundit Laekhanukit: On the Inapproximability of Parameterized Dominating Set
10:30 – 11:00: coffee break
11:00 – 11:30: Ariel Kulik: Parameterized Approximation via Fidelity Preserving Transformations
11:30 – 12:00: Eduard Eiben: Lossy Kernels for Connected Dominating Set on Sparse Graphs
12:00 – 12:30: Krzysztof Sornat: Approximation and Parameterized Complexity of Minimax Approval Voting
12:30 – 14:00: lunch
14:00 – 14:30: Euiwoong Lee: Losing Treewidth by Separating Subsets
14:30 – 15:00: Jason Li: An FPT Algorithm Beating 2-Approximation for k-Cut
15:00 – 15:30: Michael Lampis: Parameterized (Approximate) Defective Coloring
15:30 – 16:00: coffee break
16:00 – 16:30: Michael Dinitz: Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network
16:30 – 17:00: Daniel Vaz: Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs
17:00 – 17:30: Tomáš Masařík: Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
Session chairs
09:00 – 10:30: Andreas Emil Feldmann
11:00 – 12:30: Michael Lampis
14:00 – 15:30: Michael Dinitz
16:00 – 17:30: Parinya Chalermsook
Topics of interest
Parameterized approximation algorithms
Lossy kernelization
Parameterized inapproximability
Fine-grained complexity of approximation
Efficient polynomial-time approximation schemes
Location
The workshop will take place as a satellite workshop of ICALP 2018 in Prague, Czechia, on July 9th 2018. The exact times and location will be announced later. Directions to the venue can be found here.
Important dates
Submission deadline: Friday April 20th, 2018
Notification: Friday May 18th, 2018
Early registration deadline: Thursday May 31, 2018
Workshop: Monday July 9th, 2018
Registration
To participate at the workshop please register through the ICALP registration page. The fee is around 50 Euros and includes coffee during breaks and lunch (for more details see ICALP registration page).
Organizer
Andreas Emil Feldmann (feldmann.a.e@gmail.com). Please send me an email with any question you have regarding this workshop.