Problème du k-supplier
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 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.
[modifier] K-supplier minimal
- Soit
- Soit le graphe complet G = (V,E) valué par
et vérifiant l'inégalité triangulaire.
- Soit
et 
tels que 
et 
- Solution :
un k-supplier minimal est 
tel que
![\max_{v \in C} [\min_{s \in S} [W(s,v)]]](../../../math/f/d/4/fd46035d53edc21496e1f5b521036c5b.png)
est minimal
[modifier] 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 sont sur < http://brouits.free.fr/groom/kfourn.html >
