Prix EPFL de Doctorat 2020 – Jakub Tarnawski

Pour des contributions fondamentales à l’informatique théorique. En particulier, pour des progrès algorithmiques sur deux problèmes centraux de l'optimisation combinatoire, à savoir le problème du voyageur de commerce et le problème du couplage.

Dans cette thèse, nous proposons de nouveaux algorithmes pour deux problèmes de graphes fondamentaux. Nous développons de nouvelles façons d'utiliser des formulations de programmation linéaire, même de taille exponentielle, pour extraire la structure des instances de problèmes et orienter les algorithmes dans leur progression.

Dans la première partie de la thèse, nous abordons un problème de référence en optimisation combinatoire : le problème du voyageur de commerce asymétrique (ATSP). Il consiste à trouver le tour le plus court qui passent par tous les sommets d'un graphe dirigé à pondération d'arête donné. Un algorithme rho-approché pour ATSP est un algorithme qui s'exécute en temps polynomial et produit toujours un tour au plus rho fois plus long que le tour le plus court. Trouver un tel algorithme avec une constante rho était un problème ouvert de longue date. Dans la présente thèse, nous proposons un tel algorithme.

Dans la deuxième partie de la thèse, nous abordons le problème de l’appariement parfait. Nous savons depuis les années 1980 que les algorithmes parallèles sont efficaces si la randomisation est autorisée. Cependant, nous ne savons pas si cela est nécessaire - c'est-à-dire si le problème d'appariement est de la classe NC. Nous démontrons que c'est dans la classe quasi-NC. C'est-à-dire que nous donnons un algorithme parallèle déterministe qui s'exécute en temps poly-logarithmique sur de nombreux processeurs quasi-polynomiaux.