Treffer: Online and Approximation Algorithms : Beyond Worst-Case Paradigms ; 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. ...