Self-monitoring approximation algorithms

Lundi 11 décembre 2017, 14h, A 304

Ararat Harutyunyan, LAMSADE

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.

Bibliography :

[1] 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.

[2] L. Brankovic and H. Fernau. A novel parameterised approximation algorithm for minimum vertex cover. Theoretical Computer Science, 511:85—108, 2013.