Les algorithmes jouent un rôle important en informatique et sont essentiels pour plusieurs applications importantes. Le terme “algorithme” se réfère à une procédure pour résoudre un problème donné. Un tel problème peut avoir des caractéristiques et des structures différentes, et dans le cas où le problème est bien compris, des algorithmes spécifiques peuvent être conçus pour obtenir de bonnes solutions au problème en question.

La conception et l’analyse de ces algorithmes spécifiques aux problèmes ont été largement étudiées pour un large éventail de problèmes (Cormen, Leiserson, Rivest et Stein, 2001). L’objectif dans ce domaine de recherche est d’obtenir des algorithmes qui sont prouvés optimaux en ce qui concerne la capacité d’exécution et / ou d’approximation pour le problème étudié.

L’étude d’un problème spécifique nous permet d’obtenir des connaissances sur le problème en question, qui peuvent être utilisées pour le développement et l’analyse d’algorithmes spécifiques à un problème. En regardant les résultats obtenus dans ce domaine, le lecteur peut observer ce qui suit. Souvent, les algorithmes spécifiques aux problèmes sont très compliqués car ils essayent d’incorporer le plus de problèmes possible afin que de bonnes garanties sur la qualité d’exécution et / ou d’approximation puissent être prouvées.

D’un autre côté, il existe également de nombreux algorithmes randomisés simples pour lesquels de bonnes garanties de performance peuvent être données (Motwani et Raghavan, 1995). La preuve que de tels algorithmes simples fonctionnent bien est généralement plus compliquée car la connaissance du problème n’est implicitement pas présente dans l’algorithme et est élaborée dans l’analyse.