Algorithmes en ligne et d'approximation : au-delà des paradigmes pire cas

Cette thèse explore le paysage évolutif de l'analyse des algorithmes, des mesures traditionnelles du pire cas au cadre innovant des algorithmes learning augmented. Alors que l'analyse traditionnelle du pire cas a été au cœur des avancées de l'informatique théorique au cours des 50 dernières années, il existe de nombreux problèmes et algorithmes du monde réel pour lesquels l'analyse du pire cas ne fournit pas d'explication convaincante. Un exemple bien connu est le problème de la pagination en ligne, ou de la mise en cache. Dans la mise en cache, l'analyse du pire cas ne peut pas faire la distinction entre les méthodes FIFO et LRU, même si la méthode LRU est clairement supérieure en pratique. Cela sert de motivation pour explorer des approches qui vont au-delà de l'analyse du pire cas avec un accent particulier sur le domaine émergent des algorithmes avec prédictions (algorithmes learning augmented), qui a été inspiré par les progrès récents de la communauté de l'apprentissage automatique. Les algorithmes d'apprentissage automatique ont la capacité d'apprendre à partir de données passées et d'exploiter les modèles sous-jacents dans le domaine d'application, conduisant à des solutions étonnamment efficaces. Dans le cadre learning augmented, on conçoit des algorithmes qui fonctionnent en conjonction avec un modèle d'apprentissage automatique en boîte noire, qui leur fournit des informations prédictives sur les données. Étant donné que ces prédictions peuvent être sujettes à des erreurs, l'algorithme doit les gérer avec soin, une tâche qui introduit divers défis. Le cœur de notre travail réside dans les algorithmes en ligne, qui doivent prendre des décisions sans connaissance complète de la séquence d'entrée. Nous commençons par un problème purement en ligne qui illustre la nécessité d'une analyse au-delà du pire des cas. Le chapitre suivant explore une nouvelle variante d'un problème en ligne classique qui donne plus de puissance à l'algorithme en ligne en fournissant des informations supplémentaires sur l'entrée. Dans les deux chapitres suivants, nous étudions deux problèmes en ligne différents à travers le prisme des algorithmes learning augmented. Nous concevons des algorithmes utilisant des prédictions qui surmontent les barrières computationnelles connues lorsque les prédictions sont suffisamment précises. Même lorsque les prédictions sont mauvaises, nos algorithmes maintiennent toujours des garanties du pire des cas qui sont proches des meilleures garanties réalisables sans prédictions. Enfin, nous introduisons des schémas d'approximation learning augmented pour les problèmes d'optimisation NP-difficiles. Nous montrons que même un petit nombre de prédictions suffit à améliorer le temps d'exécution d'algorithmes d'approximation bien connus, dépassant les limites de calcul connues de l'analyse du pire cas.