L'Académie nationale des sciences recompense Ola Svensson

Ola Svensson a livré une série de nouveaux algorithmes révolutionnaires pour le problème du vendeur itinérant, l'une des questions les plus étudiées et les plus importantes en informatique théorique.

Le problème du vendeur itinérant consiste à déterminer le chemin le plus court qu'une personne peut emprunter lorsqu'elle visite un certain nombre de villes et ensuite retourne à son point d'origine. Posé pour la première fois en 1930, le problème est considéré comme une référence en matière d'optimisation. 

En 2011, Professeur Svensson a écrit un nouvel algorithme primé pour le problème du vendeur itinérant symétrique qui a développé des percées dans l'optimisation computationnelle et les algorithmes de graphes théoriques. Il a a également présenté une nouvelle approche pour la variante asymétrique en 2015. Deux autres articles cosignés ont suivi, aboutissant à la première garantie d'approximation à facteur constant et apportant collectivement plusieurs nouvelles idées dans le domaine de l'optimisation combinatoire. 

En dehors du problème des vendeurs itinérants, le travail d'Ola Svensson a apporté d'autres idées nouvelles, dont la plus récente consiste à dé-randomiser un algorithme probabiliste qui a été au cœur des recherches pendant près de trois décennies.

Le Prix Michael et Sheila Held est décerné chaque année. Ce prix de 100 000 $ récompense des recherches exceptionnelles, innovantes, créatives et influentes dans les domaines de l'optimisation combinatoire et discrète, ou dans des domaines liés à l'informatique, tels que la conception et l'analyse des algorithmes et la théorie des complexes. Ce prix vise à reconnaître les travaux récents (définis comme ayant été publiés au cours des huit dernières années). Il a été créé en 2017 par l'héritage de Michael et Sheila Held.