A note on probably certifiably correct algorithms

De nombreux problèmes d'optimisation, bien qu'ils soient difficiles à traiter dans les cas les plus compliqués, peuvent souvent être résolus de manière efficace par des heuristiques lorsque les données du problème sont tirées au hasard (données typiques). Malheureusement, dans la plupart des cas, on ne sait que rarement certifier si l'heuristique produit une solution optimale au problème. Dans cette note, nous décrivons une famille d'algorithmes qui non seulement résolvent le problème sur des données typiques, mais aussi produisent un certificat d'optimalité. À titre d'illustration, nous décrivons un tel algorithme pour le problème du partitionnement de graphe dans le modele stochastique à blocs. D'autres exemples sont aussi discutés brièvement.