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[modifier | modifier le code]

Soit $k\in \mathbb {N} ^{+}$ et soit le graphe complet $G=(V,E)$ valué par $C:V\rightarrow \mathbb {N} ^{+}$ et $W:E\rightarrow \mathbb {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$ . 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 minimum.

Complexité et approximation[modifier | modifier le code]

Le 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 | modifier le code]

↑ 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, 1990, 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, n^o 3,‎ 1986, p. 533-550