|
Méthodes pour l'estimation du temps de calcul d'un algorithme de branchement : de l'analyse standard à "Partition & Measure"| old_uid | 11210 |
|---|
| title | Méthodes pour l'estimation du temps de calcul d'un algorithme de branchement : de l'analyse standard à "Partition & Measure" |
|---|
| start_date | 2012/04/02 |
|---|
| schedule | 14h |
|---|
| online | no |
|---|
| summary | La recherche d'algorithmes en temps modérément exponentiel (plus rapides qu'une approche en force brute) pour les problèmes NP-difficiles est un champ très actif en algorithmique et théorie des graphes depuis une vingtaine d'années. Parmi eux, les algorithmes de branchements (récursifs) sont les plus répandus. L'analyse au pire des cas de la complexité de ces algorithmes a subi une importante évolution avec la définition en 2005 de mesures non-standards (paradigme "Measure & Conquer"). Aujourd'hui nous proposons une nouvelle approche qui permet d'améliorer de façon systématique la borne sur le temps de calcul de ces algorithmes. |
|---|
| responsibles | Renard |
|---|
| |
|