Problème du k-supplier
(Redirigé depuis 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
modifierSoit 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
modifierLe problème est NP-complet. Il existe un algorithme d'approximation de ratio 3[1], et ce ratio est optimal si P est différent de NP[2].
Notes et références
modifier- Qingzhou Wang et Kam-Hoi Cheng, « A Heuristic Algorithm for the k-Center Problem with Vertex Weight », dans Algorithms, International Symposium {SIGAL} '90, Tokyo, Japan, August 16-18, 1990, Proceedings, , p. 388-396
- Dorit S. Hochbaum et David B. Shmoys, « A unified approach to approximation algorithms for bottleneck problems », Journal of the ACM, vol. 33, no 3, , p. 533-550
Voir aussi
modifierArticles connexes
modifierLiens externes
modifier- (en) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski et Gerhard Woeginger, « Minimum k-supplier », sur A compendium of NP optimization problems,
- Une formulation du problème et quelques liens