Probleme du k-supplier

Problème du k-supplier

Le problème du k-supplier minimal est un problème de théorie des graphes. Il s'apparente au problème du k-centre minimal mais en supprime la notion intuitive de centre.

En quelques mots, 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.

K-supplier minimal

• Soit $k \in \N^+$
• Soit le graphe complet G = (V,E) valué par
  • $C : V \rightarrow \N^+$
  • $W : E \rightarrow \N^+$

et vérifiant l'inégalité triangulaire.

• Soit $F \subset V$ et $C \subset V$ tels que $F \cap C = \emptyset$ et $F \cup C = V$
• Solution :

un k-supplier minimal est $S \subseteq F$ tel que

• $\sum_{v \in S} C(v) \leq k$
• $\max_{v \in C} [\min_{s \in S} [W(s,v)]]$ est minimal

Références

• Un algorithme d'approximation polynomial trouvant une solution de rapport constant a été énoncé dans A unified approach to approximation algorithms for bottleneck problems, (Journal of the Association for Computing Machinery) vol.33 n.3 (Jul 1986) 533-550.

• Une formulation du problème et quelques liens

Ce document provient de « Probl%C3%A8me du k-supplier ».