MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEDifficulté d'instance et instances difficiles
par Valentin Weber, G-SCOP, Grenoble
| Date : | 04/01/11 | | Time : | 10:30 | | Location : | Galois Coriolis |
Dans la conception d'algorithmes, il y a deux manières courantes d'évaluer la qualité des algorithmes. Pour les algorithmes d'approximation, une garantie de performance est déterminée théoriquement. Même dans le pire cas, la valeur des solutions est à une distance garantie de la valeur optimale. Autrement, le comportement des algorithmes est évalué de manière empirique à ' travers le benchmarking. Les algorithmes sont testés sur un ensemble d'instances. Le choix de ces instances est cependant crucial pour la pertinence des résultats attendus. Malgré la présence d'algorithmes d'approximation, la pratique recommande parfois plutôt des algorithmes sans garantie. Ces deux approches, soit purement théorique, soit purement empirique, sont donc très éloignées. Pour évaluer plus précisément la qualité en pratique des algorithmes, nous souhaitons enrichir l'approche empirique par des résultats théoriques et une méthodologie rigoureuse. En particulier, notre réflexion principale repose sur la pertinence des instances choisies comme référence. Nous proposons des méthodes pour générer des instances qui reflètent la difficulté du problème sous-jacent. Nous illustrerons nos propos en nous appuyant sur le problème du Voyageur de Commerce.
Page des séminaires
| 
