Algorithmes en ligne

Les algorithmes en ligne doivent prendre des décisions irrévocables au fur et à mesure de l'arrivée des données, sans connaître les requêtes futures ; leur qualité est évaluée par une analyse compétitive par rapport à un algorithme optimal qui dispose de l'ensemble des données à l'avance.

Definition

Un algorithme en ligne reçoit ses données sous la forme d'une séquence de requêtes et doit répondre à chacune immédiatement et de manière irrévocable, sans avoir connaissance des requêtes futures ; son ratio de compétitivité représente le rapport, dans le pire des cas, entre son coût et celui d'un algorithme hors ligne optimal qui connaît l'intégralité de la séquence de requêtes.

Scope

Ce domaine aborde les algorithmes qui traitent les données séquentiellement et prennent des décisions irrévocables avant que les données ultérieures ne soient connues, ainsi que le cadre du ratio de compétitivité utilisé pour les évaluer face à un adversaire hors ligne optimal. Il englobe des problèmes classiques tels que la pagination et la mise en cache, la mise à jour de listes, le problème de la location de skis, le problème du k-serveur, l'ordonnancement en ligne et le problème du remplissage de bacs, de même que le rôle de la randomisation dans l'amélioration des ratios de compétitivité face à des adversaires moins puissants.

Core questions

• Comment les algorithmes en ligne sont-ils évalués lorsque le futur est inconnu ?
• Que mesure le ratio de compétitivité, et qu'est-ce que l'adversaire hors ligne ?
• Comment des problèmes classiques comme la pagination et la location de skis illustrent-ils les compromis en ligne ?
• Comment la randomisation peut-elle améliorer la compétitivité face à un adversaire ignorant ?
• Quelles bornes inférieures limitent la compétitivité de tout algorithme en ligne ?

Key concepts

• en ligne versus hors ligne
• ratio de compétitivité
• adversaire hors ligne
• pagination et mise en cache
• mise à jour de listes
• problème de la location de skis
• problème du k-serveur
• compétitivité randomisée

Key theories

Analyse compétitive

L'analyse compétitive évalue un algorithme en ligne en se basant sur le rapport, dans le pire des cas, entre son coût et celui d'un algorithme hors ligne optimal, fournissant ainsi une garantie qui s'applique à toute séquence d'entrée, sans dépendre d'hypothèses sur les données.

Randomisation contre les adversaires ignorants

Les algorithmes en ligne randomisés peuvent atteindre des ratios de compétitivité strictement supérieurs à ceux de tout algorithme déterministe face à un adversaire ignorant, car ce dernier doit fixer les données d'entrée sans connaître les choix aléatoires de l'algorithme.

Clinical relevance

Les algorithmes en ligne modélisent les décisions que les systèmes prennent en temps réel sans connaissance préalable du futur : le remplacement de cache et de pages dans les systèmes d'exploitation et les CPU, l'auto-organisation des structures de données, l'allocation dynamique des ressources et l'équilibrage de charge, ainsi que les décisions d'achat ou de location dans le cloud computing. L'analyse compétitive fournit des garanties dans le pire des cas pour ces systèmes réactifs.

History

L'analyse compétitive a été introduite par Sleator et Tarjan en 1985, suite à leurs travaux sur les règles de mise à jour de listes et de pagination, redéfinissant l'évaluation des algorithmes en ligne par une comparaison avec une solution hors ligne optimale. Ce cadre s'est développé avec le problème du k-serveur et les algorithmes en ligne randomisés dans les années 1990, comme en témoigne la monographie de Borodin et El-Yaniv de 1998.

Key figures

• Daniel Sleator
• Robert Tarjan
• Allan Borodin
• Ran El-Yaniv

Seminal works

• sleator1985
• borodin1998
• cormen2009

Frequently asked questions

Qu'est-ce que le ratio de compétitivité ?

Il s'agit du rapport, dans le pire des cas, entre le coût d'un algorithme en ligne et celui d'un algorithme optimal qui dispose de l'intégralité des données à l'avance. Un algorithme 2-compétitif ne coûte jamais plus du double du meilleur coût hors ligne possible pour toute séquence d'entrée.

Pourquoi la randomisation aide-t-elle les algorithmes en ligne ?

Face à un adversaire ignorant qui fixe les données d'entrée sans connaître les choix aléatoires de l'algorithme, la randomisation empêche cet adversaire de concevoir un scénario du pire cas spécifiquement adapté au comportement de l'algorithme, ce qui permet d'atteindre des ratios de compétitivité strictement supérieurs à ceux que tout algorithme déterministe pourrait obtenir.