Department of
Applied
Mathematics

Recent Advancements at the Intersection of Parameterized and Approximation Algorithms

Andreas Feldmann

MFF UK

Abstract

Two standard approaches to handle NP-hard optimization problems are to develop approximation and parameterized algorithms. 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. Lately there has been a great deal of development in proving the existence or non-existence of parameterized approximation algorithms. In this talk I will present several recent results for variants of Steiner network problems (e.g. the classical Steiner tree problem). I will introduce the used techniques for each result, which are inspired by approximation algorithms and parameterized algorithms for similar problems. No previous knowledge about approximation and parameterized algorithms will be assumed.