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) |
ABSTRACT
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.
References:
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
