Evènement pour le groupe Séminaire du LaBRI

Date 2009-06-04  14:30-15:30
TitreSém. LaBRI. Moderately exponential time algorithms 
RésuméSome important part of the research on design and analysis of algorithms is trying to find better approaches for solving NP-hard problems. In most cases the notion of "solving a problem exactly" is relaxed: approximation algorithms, heuristics, randomized algorithms, parameterized algorithms, algorithms for restricted inputs, etc. Another approach, called moderately exponential-time algorithms, has attracted a lot of interest recently. Such an algorithm indeed tries to cope with NP-hardness in the strongest sense: the problem needs to be solved by the algorithm for all inputs and worst-case running time is considered. Techniques for the design and analysis of moderately exponential-time algorithms will be presented, among them branching algorithms, dynamic programming algorithms and inclusion exclusion algorithms. The breakthrough result of Bjorklund, Husfeldt and Koivisto (FOCS 2006), a O*(2^n) algorithm to compute the chromatic number of an n-vertex graph will be outlined. 
Lieusalle 178 
OrateurDieter Kratsch 
UrlUniversité Paul Verlaine - METZ 

Aucun document lié à cet événement.

Retour à l'index