A satellite workshop of ICALP 2024 taking place in Tallinn, Estonia, on Saturday July 6th 2024.

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.

Contributed talks and schedule

session 1:

• 09:00: Matthias Kaul: "A (1.5+$\varepsilon$)-Approximation for Multiple TSP with a Variable Number of Depots"

• 09:30: George Osipov: "Constant-Factor FPT-Approximation Dichotomies for MinCSPs"

• 10:00 - 10:30: coffee

session 2:

• 11:00: Ilan Doron-Arad: "Budgeted Matroid Maximization: a Parameterized Viewpoint"

• 11:30: Andreas Emil Feldmann: "A Parameterized Approximation Scheme for Steiner Forest in Bounded Treewidth Graphs"

• 12:00 - 14:00: lunch

session 3:

• 14:00: Ameet Gadekar: "Parameterized Approximation Schemes for Clustering with General Norm Objectives"

• 14:30: Fateme Abbasi: "Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces"

• 15:00: Tanmay Inamdar: "FPT approximation for Clustering with Outliers"

• 15:30 - 16:00: coffee

session 4:

• 16:00: Mahdi Cheraghchi: "Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All $l_p$ Norms"

• 16:30: Shuangle Li: "Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH"

• 17:00: open problem session

Location

The workshop will take place as a satellite workshop of ICALP 2024 in Tallinn, Estonia, on July 6th 2024.