inscriptions : 0/0 Registrations
Résumé : Self-monitoring approximation algorithms
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.
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.
Lieu : A407
Résumé : Graphs allow to encode structural information included within data used in chemical or pattern recognition problems. However, conversely to vectors defined in an euclidean space, the definition of a graph (dis)similarity measure is not straightforward, but required to compute prediction models. One of the most well known dissimilarity measure is the graph edit distance. Despite its good interpretability, the computation of a graph edit distance between two graphs is an NP-Hard
problem. Therefore, its application remains limited to small graphs. During this presentation, I will introduce a formal definition of this metric between graphs as a quadratic assignment problem and some methods used in pattern recognition to approximate an optimal solution. Considering approximations allows us to apply this framework to chemoinformatics problems.