Nos tutelles

CNRS Dauphine PSL *



20 mars 2018: 2 événements


  • Séminaires du Pôle 2 : "Optimisation combinatoire, algorithmique"

    Du 26 février 14:00 au 1er avril 15:30 - Henning Fernau

    Séminaires du Pôle 2 : "Optimisation combinatoire, algorithmique"

    inscriptions : 0/0 Inscriptions

    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

    En savoir plus : Séminaires du Pôle 2 : "Optimisation combinatoire, algorithmique"
  • Séminaires du Pôle 3 : "Sciences des données"

    Mardi 20 mars 11:00-12:00 - Benoît Gaüzère - INSA de Rouen/LITIS

    Séminaires du Pôle 3 : "Sciences des données"

    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.

    En savoir plus : Séminaires du Pôle 3 : "Sciences des données"