Le problème du k-supplier minimum est un problème algorithmique de théorie des graphes.
Il s'agit de trouver sous contrainte un ensemble réparti de sommets « fournisseurs » tel que le reste des sommets du graphe, les « clients », aient dans leur voisinage un sommet « fournisseur » qui leur soit le plus proche possible. Rechercher un tel ensemble dans un graphe est un problème NP-complet.
Définition formelle Soit et soit le graphe complet valué par et et vérifiant l'inégalité triangulaire. Soit et tels que et . Un k-supplier minimal est tel que :
est minimum.
Complexité et approximation
Le problème est NP-complet. Il existe un algorithme d'approximation de ratio 3, et ce ratio est optimal si P est différent de NP.
Notes et références
Voir aussi
Articles connexes k-moyennes k-médiane k-centre
Liens externes
Une formulation du problème et quelques liens
k-supplier