Henning Fernau

Self-monitoring approximation algorithms

VCLA hosted a talk by Henning Fernau

DATE:Monday, April 9, 2018
TIME:17:00 c.t.
VENUE:Seminar Room Neumann, Favoritenstrasse 9-11, Ground Floor, (HB EG 16)


Reduction rules are one of the key techniques for the design of parameterized algorithms. They can be seen as formalizing a certain kind of heuristic approach to solving hard combinatorial problems. We propose to use such a strategy in the area of approximation algorithms. One of the features that we may gain is a self-monitoring property. This means that the algorithm that is run on a given instance I  can predict an approximation factor of the solution produced on I that  is often (according to experiments) far better than the theoretical estimate that is based on a worst-case analysis.


F.N. Abu-Khzam, C. Bazgan, M. Chopin, and H. Fernau. Data reductions and combinatorial bounds for improved approximation algorithms. Journal of Computer and System Sciences, 82:503-520, 2016.

L. Brankovic and H. Fernau. A novel parameterised approximation algorithm for Minimum Vertex Cover. Theoretical Computer Science, 511:85-108, 2013.


Henning Fernau, Trier University

Comments are closed.