Procrastiner en toute confiance : Configuration algorithmique adaptative quasi-optimale, à tout moment.

Les méthodes de configuration d'algorithmes optimisent la performance d'un algorithme heuristique paramétré sur une distribution donnée d'instances de problèmes. Des travaux récents ont introduit une procédure de configuration d'algorithme ("Procrastination structurée") qui permet d'obtenir de manière prouvée des performances quasi optimales avec une probabilité élevée et un temps d'exécution presque minimal dans le pire des cas. Elle offre également une propriété "anytime" : elle continue à renforcer ses garanties d'optimalité au fur et à mesure de son exécution. Malheureusement, la procrastination structurée ne s'adapte pas aux caractéristiques de l'algorithme paramétré : elle traite chaque entrée comme le pire des cas. Un travail ultérieur ("LeapsAndBounds") permet d'obtenir une adaptabilité, mais sans la propriété "anytime". Cet article présente un nouvel algorithme, "Procrastination structurée avec confiance", qui préserve les propriétés de quasi-optimalité et de disponibilité de la Procrastination structurée tout en ajoutant de l'adaptabilité. En particulier, le nouvel algorithme sera beaucoup plus rapide dans des contextes où de nombreuses configurations d'algorithmes sont peu performantes. Nous montrons empiriquement que de telles situations sont fréquentes dans la pratique et que la propriété anytime est utile pour trouver rapidement de bonnes configurations.