A satellite workshop of ICALP 2019 taking place in Patras, Greece, on Monday July 8th 2019.

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.

Open problems

A list of open problems presented during the workshop can be found here.

Contributed talks

All talks take place in room II.9.

09:30 - 10:00: Andreas Emil Feldmann: Parameterized Approximation Algorithms for Bidirected Steiner Network Problems

10:00 - 10:30: Ljiljana Brankovic: Combining Two Worlds: Parameterised Approximation for Vertex Cover

10:30 - 11:00: Cornelius Brand: Extensor-Coding: Parameterized Approximation through Abstract Algebraic Methods

11:00 - 11:30: coffee break

11:30 - 12:00: Jan Marcinkowski: Constant Factor FPT Approximation for Capacitated k-Median

12:00 - 12:30: Jason Li: Tight FPT Approximations for k-Median and k-Means

12:30 - 13:00: Johannes Blum: Inapproximability of k-Center on gerGraphs of Low Skeleton Dimension

13:00 - 14:30: lunch break

14:30 - 15:00: Bundit Laekhanukit: Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses

15:00 - 15:30: Bingkai Lin: A Simple Gap-producing Reduction for the Parameterized Set Cover Problem

15:30 - 16:00: coffee break

16:00 - 16:30: Lars Rohwedder: Empowering the Configuration-IP − New PTAS Results for Scheduling with Setup Times

16:30 - 17:00: Mingyu Xiao: New Results on Polynomial Inapproximability and Fixed Parameter Approximability of Edge Dominating Set

17:00 - 18:00: open problem session

Location

The workshop will take place as a satellite workshop of ICALP 2019 in Patras, Greece, on July 8th 2019. Directions to the venue can be found here.