Nos tutelles

CNRS Dauphine PSL *



2 mars 2018: 1 événement


  • 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"