K-centre
# K-centre

Le problème k-centre (k-center problem en anglais) est un problème d'optimisation combinatoire, une branche de l'algorithmique. Le problème peut se décrire de façon informelle ainsi : étant donné n villes, il faut ouvrir une caserne de pompiers dans k villes, tel que la distance entre chaque ville et la plus proche caserne soit minimisée.

De façon plus formelle, il s'agit, étant donné un ensemble de points V, de choisir un sous-ensemble de k points, appelés centres, tel que le maximum des distances des points de V au plus proche centre soit minimisée. Dans la majorité des cas on considère implicitement que l'espace est métrique, le problème s'exprime alors naturellement comme un problème sur un graphe dont les arêtes ont des poids respectant l'inégalité triangulaire.

Ce problème est surtout étudié du point de vue de l'approximation. Il en existe plusieurs variantes, avec des métriques particulières, ou d'autres coûts à minimiser. Une application différente du placement d'installations, est le partitionnement de données (clustering).

## Définition formelle

Le problème s'exprime de la façon suivante dans le cas métrique.

Étant donné un entier k et un graphe complet non-orienté G = (V, E) dont les distances $d(v_i,$ $v_j)$ ∈ N respectent l'inégalité triangulaire, trouver un sous-ensemble S ⊆ V avec |S| = k qui minimise: $\max _{v\in V}\min _{s\in S}d(v,s)$. Autrement dit on considère le problème d'optimisation dont la fonction objectif est $\min _{S\subseteq V:|S|=k}\max _{v\in V}\min _{s\in S}d(v,s)$.

Le cas général sans métrique est peu étudié car trop difficile même du point de vue de l'approximation. Plus précisément, sans hypothèse le problème n'est pas dans APX. Le reste de l'article traite implicitement du cas métrique.

## Complexité

Le problème est NP-complet dans sa version problème de $décision^,.$

## Approximation

Il existe des algorithmes d'approximation de ratio 2, et si P est différent de NP ce résultat est optimal.

### Algorithme glouton

L'algorithme glouton suivant a été proposé par Gonzalez en 1985. Il est parfois appelé farthest first traversal.

* Choisir un premier sommet arbitraire et en faire un centre.
* Faire k-1 fois :
   * Trouver un sommet dont la distance aux centres déjà ouverts est maximale
   * En faire un centre.

La solution calculée est dans le pire cas, deux fois moins bonne que la solution optimale. On le prouve rapidement. À la fin de l'algorithme, soit r la distance maximale d'un point à un centre, et soit p un tel point. Soit S l'ensemble constitué des centres et de p. L'ensemble S a k+1 points à distance au moins r les uns des autres. Alors dans la solution optimale, au moins deux points de S doivent partager un même centre (il y a plus de points dans S que de centres dans la solution optimale). D'après l'inégalité triangulaire, au moins l'un de ces points partageant le même centre est à distance r/2 d'un centre.

La complexité en temps de l'algorithme est O(nk).

### Méthode du seuil

On peut obtenir une 2-approximation par la méthode du seuil (ou threshold method aussi appelé parametric $pruning^,).$ Elle consiste à tester toutes les solutions possibles : la valeur optimale étant un coût présent sur une arête, le nombre d'arêtes est polynomial et on peut faire un test polynomial pour chaque valeur. Le test consiste à enlever les arêtes de poids supérieurs et à vérifier que l'on peut obtenir une 2-approximation dans le graphe élagué.

Cet algorithme est dû à Hochbaum et Shmoys.

### Difficulté d'approximation

Le problème est NP-difficile à approcher pour un ratio inférieur à 2. Ce résultat est dû à Hsu et Nemhauser. La preuve donnée ci-dessous est une réduction au problème de l'ensemble dominant.

Soit une instance (G,k) pour le problème de l'ensemble dominant. On la transforme en une instance G' , le graphe complet ayant les mêmes sommets, avec les poids suivants sur les arêtes : 1 pour les arêtes de G, et 2 pour les autres. Si l'ensemble dominant est de taille inférieure à k alors G' a une solution k-centre de coût 1, sinon une solution de coût 2. Ainsi un algorithme d'approximation de ratio inférieur à 2, donne une réponse pour le problème de l'ensemble dominant qui est lui-même NP-difficile.

### Cas particuliers

Si le graphe est planaire il existe un schéma d'approximation en temps polynomial pour le problème.

## Variantes, problèmes liés et applications

Un cas particulier est celui ou la métrique est euclidienne, parfois appelé k-centre géométrique.

Une façon classique de modifier le problème est de rajouter des capacités différentes aux centres. Ainsi un certain nœud, s'il est choisi comme centre, ne pourra servir qu'un nombre restreint de voisins.

Le problème k-médiane, utilise le même cadre, mais avec une autre fonction à minimiser. Dans le problème de l'emplacement d'installations (facility location problem), on remplace le paramètre k par des coûts d'ouverture et de liaison.

La calcul d'un k-centre peut permettre de faire du partitionnement de données. Les distances représentent alors des similarités, comme pour les k-moyennes.

