Vers Une Définition Formelle des Algorithmes Gloutons

1. Résumé du projet

Les algorithmes gloutons sont parmi les premiers types d’algorithmes enseignés dans un programme standard de premier cycle en informatique. Intuitivement, un algorithme est appelé glouton s’il tente d’optimiser une fonction d’objectif globale en prenant localement des décisions optimales. Le principe qui sous-tend la conception d’un algorithme glouton peut être résumé de manière succincte comme «vivant pour aujourd’hui». De nombreux problèmes d’optimisation ont une entrée pouvant être représentée sous la forme d’une séquence d’éléments, tandis que les sorties est une séquence de décisions – une décision par élément, telle que d’accepter ou de rejeter cet élément d’entrée, par exemple. Dans de nombreux cas, un algorithme glouton traite les éléments d’entrée dans un ordre quelconque et prend une décision optimale en supposant que l’élément en cours est l’élément d’entrée final. Il est généralement facile de concevoir des algorithmes gloutons pour un problème donné, mais il peut être assez difficile de les analyser. Il est assez rare qu’un algorithme glouton parvienne à l’optimalité, bien que cela se produise (par exemple, les algorithmes de Prim et de Kruskal pour le problème de l’arbre couvrant minimal et le premier algorithme de temps de finition pour la planification par intervalles). Malgré cela, les algorithmes gourmands sont importants et largement utilisés, car ils ont tendance à être très efficaces, leurs temps d’execution est souvent linéaire ou presque linéaire. De plus, les algorithmes gloutons offrent souvent des garanties de performance raisonnables en termes d’approximation, même dans le cas le plus défavorable, correspondant parfois aux meilleures limites d’inapproximabilité. Les algorithmes gloutons ont tendance à être encore meilleurs dans la pratique, bien au-delà de leurs garanties les pires.

Alors que la définition intuitive de ce que cela signifie pour un algorithme d’être glouton est suffisante dans de nombreux cas, elle ne permet pas d’établir une étude systématique d’algorithmes gloutons. Plus important encore, une définition intuitive ne suffit pas pour répondre aux questions concernant les limites des algorithmes gloutons. Supposons qu’il existe un algorithme glouton qui permet d’obtenir un rapport d’approximation α pour certains problèmes d’optimisation et que l’on soupçonne fortement qu’aucun autre algorithme glouton ne pourrait atteindre un meilleur taux d’approximation. Comment peut-on prouver un tel résultat ? Cela nécessite une définition formelle des algorithmes gloutons. La première tentative pour donner une telle définition peut être attribuée à l’établissement de la théorie des matroïdes en 1935 par Whitney (biens avant la définition informelle d’algorithmes gloutons en optimisation combinatoire par Edmonds). Plus tard, il fut généralisé à la théorie des greedoid par Korte et Lovász. Malgré les liens profonds qui existent entre les greedoids et les problèmes posés par des solutions optimales gloutons, il n’existe à ce jour aucune définition formelle des algorithmes gloutons largement acceptée. L’une des tentatives les plus récentes de formalisation d’algorithmes gloutons est le cadre de priorités de Borodin, Nielsen et Rackoff. L’objectif principal de ce projet de recherche est d’étudier ce cadre plus en profondeur et de proposer des modifications au modèle qui pourraient mieux représenter des algorithmes gloutons.