Parsimonious advice and tradeoffs in learning-augmented algorithms

Prédictions parcimonieuses et compromis dans les algorithmes avec prédictions Cette thèse explore plusieurs questions fondamentales dans le domaine des algorithmes augmentés par l'apprentissage, un paradigme dans lequel l'algorithme doit opérer sous incertitude, en disposant de prédictions potentiellement inexactes sur les paramètres inconnus du problème. Le principal défi réside dans l'absence de garanties sur la qualité de ces prédictions. L’objectif est de concevoir des algorithmes capables de tirer efficacement parti de prédictions précises pour améliorer les performances, tout en restant robustes et compétitifs lorsque les prédictions sont erronées.La thèse est structurée en deux parties principales, chacune abordant un aspect distinct de ce défi.La première partie s’intéresse aux situations dans lesquelles l’accès aux prédictions est limité, que ce soit en raison de coûts, de contraintes budgétaires ou d'une disponibilité partielle des predictions. Cette restriction impose une utilisation soigneuse et stratégique des predictions disponbiles. En analysant des problèmes séquentiels classiques tels que extit{ski rental}, le problème des extit{secretaires}, l’ extit{ordonnancement} et la conception de extit{files de priorité}, cette partie montre que même un accès partiel aux prédictions permet d'obtenir une fortes performance, avec des algorithmes efficaces. Les approches développées interpolent entre les solutions purement en ligne et celles totalement informées.La seconde partie examine les compromis fondamentaux liés à la conception d’algorithmes augmentés par l’apprentissage. Elle se concentre notamment sur l’équilibre entre trois critères de performance clés : la cohérence (performance améliorée lorsque les prédictions sont précises), la robustesse (performance assez correcte face à de mauvaises prédictions) et la dégradation progressive des performances en fonction de la qualité des prédictions. Cette partie propose des algorithmes améliorés pour des problèmes classiques tels que extit{one-max search} et le problème d'ordonnancement non clairvoyant, surmontant certaines faiblesses identifiées dans les travaux antérieurs sur ces problèmes.