Algorithme d'approximation pour le problème du k-fournisseur (k-supplier)

Ecole: UNIVERSITE EVRY-VAL-D'ESSONNE - EVRY
Entreprise: aucune
Niveau: BAC + 5
Dans le cadre de système distribués, informatiques ou non, notamment dans les environnements de travail de groupe, on est confronté à des problèmes de communication, de performance et de sûreté de l'infrastructure. On trouve entre autres des problème de choix, ou d'élection de points particuliers par lesquels doibent passer l'information. Le problème étudié est un problème d'élection de sommets sur un graphe muni de clients et de fournisseurs potentiels. La complexité de résolution de ce problème n'est pas polynomiale. Nous allons proposer un algorithme d'approximation polynomial.