The Parameterized Approximation Algorithms Workshop (PAAW) will take place
as a satellite workshop of ICALP 2019 in Patras, Greece, on Monday July 8th
2019.
https://sites.google.com/site/aefeldmann/parameterized-approximation-algorithms-workshop-paaw-2019
--- Registration ---
To participate at the workshop please register through the ICALP
registration page (early registration deadline is June 9th 2019):
https://icalp2019.upatras.gr/regis.php#ele-8
--- Contributed talks ---
- Johannes Blum: Inapproximability of k-Center on Graphs of Low Skeleton
Dimension
- Cornelius Brand: Extensor-Coding: Parameterized Approximation through
Abstract Algebraic Methods
- Andreas Emil Feldmann: Parameterized Approximation Algorithms for
Bidirected Steiner Network Problems
- Klaus Jansen: Empowering the Configuration-IP − New PTAS Results for
Scheduling with Setup Times
- Jason Li: Tight FPT Approximations for k-Median and k-Means
- Bingkai Lin: A Simple Gap-producing Reduction for the Parameterized Set
Cover Problem
- Jan Marcinkowski: Constant Factor FPT Approximation for Capacitated
k-Median
- Mingyu Xiao: New Results on Polynomial Inapproximability and Fixed
Parameter Approximability of Edge Dominating Set
--- 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.
--- Topics of interest ---
- Parameterized approximation algorithms
- Lossy kernelization
- Parameterized inapproximability
- Fine-grained complexity of approximation
- Subexponential time approximation
- Efficient polynomial-time approximation schemes
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
