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.

Soit ${\displaystyle k\in \mathbb {N} ^{+}}$ et soit le graphe complet ${\displaystyle G=(V,E)}$ valué par ${\displaystyle C:V\rightarrow \mathbb {N} ^{+}}$ et ${\displaystyle W:E\rightarrow \mathbb {N} ^{+}}$ et vérifiant l'inégalité triangulaire. Soit ${\displaystyle F\subset V}$ et ${\displaystyle C\subset V}$ tels que ${\displaystyle F\cap C=\emptyset }$ et ${\displaystyle F\cup C=V}$. Un k-supplier minimal est ${\displaystyle S\subseteq F}$ tel que :

• ${\displaystyle \sum _{v\in S}C(v)\leq k}$
• ${\displaystyle \max _{v\in C}\min _{s\in S}W(s,v)}$ est minimum.

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].

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

• (en) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski et Gerhard Woeginger, « Minimum k-supplier », sur A compendium of NP optimization problems, 2000
• Une formulation du problème et quelques liens

• Portail de l'informatique théorique