Résumé | Dans cette présentation, nous nous intéressons à l'orientation de graphe de manière distribuée. Plus précisément, nous cherchons à calculer une orientation minimum, c'est-à-dire à minimiser le degré sortant maximum d'un nœud du graphe. Ce problème d'orientation est notamment une modélisation naturelle pour des problèmes d'allocation de ressources. Nous présentons l'algorithme AvgDegAsync qui fonctionne dans un environnement distribué où les communications sont asynchrones et où les nœuds peuvent être en panne. Notre algorithme garantit une $2(2+epsilon)$-approximation de l'orientation optimale en utilisant un nombre logarithmique de rondes asynchrones. De plus, il ne nécessite pas de connaissance sur le graphe comme le nombre de nœuds ou encore sa densité.
Ce travail a été réalisé avec Nicolas Hanusse et une présentation a été donnée à AlgoTel 2017 |