Supervisory authorities

CNRS Dauphine PSL *

Search





Home

20 March 2018: 2 events

séminaire

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

    From 26 February 14:00 to 1 April 15:30 - Henning Fernau

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

    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

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

    Tuesday 20 March 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"