Parameterized Approximation Algorithms Workshop (PAAW)

2019: Patras, Greece

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


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.

Schedule of contributed talks


Previous workshops

Topics of interest

  • Parameterized approximation algorithms
  • Lossy kernelization
  • Parameterized inapproximability
  • Fine-grained complexity of approximation
  • Subexponential time approximation
  • Efficient polynomial-time approximation schemes


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

Important dates

  • Submission deadline: Friday April 26th, 2019
  • Notification: Friday May 17th, 2019
  • Early registration deadline: Thursday May 30, 2019
  • Workshop: Monday July 8th, 2019


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).


Andreas Emil Feldmann ( Please don't hesitate to send me an email with any question you have regarding this workshop.