Problème du k-supplier

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 $k\in {\mathbb{N}}^{+}$ et soit le graphe complet $G=(V,E)$ valué par $C:V\to {\mathbb{N}}^{+}$ et $W:E\to {\mathbb{N}}^{+}$ et vérifiant l'inégalité triangulaire. Soit $F\subset V$ et $C\subset V$ tels que $F\cap C=\mathrm{\varnothing }$ et $F\cup C=V$. Un k-supplier minimal est $S\subseteq F$ tel que :

• $\sum _{v\in S}C(v)\le k$
• $\underset{v\in C}{\max }\underset{s\in S}{\min }W(s,v)$ 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.

Voir aussi

Articles connexes

• k-moyennes
• k-médiane
• k-centre

Liens externes

• Modèle:Lien web
• Une formulation du problème et quelques liens