Résumé en anglais

We present in this paper general pseudo-polynomial time algorithms to solve min-maxand min-max regret versions of some polynomial or pseudo-polynomial problems undera constant number of scenarios. Using easily computable bounds, we can improve thesealgorithms. This way we provide pseudo-polynomial algorithms for the min-max and andmin-max regret versions of several classical problems including minimum spanning tree,shortest path, and knapsack.