K-centre

Le problème k-centre (k-center problem en anglais^[1]) 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: ${\displaystyle \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 ${\displaystyle \min _{S\subseteq V:|S|=k}\max _{v\in V}\min _{s\in S}d(v,s)}$^[2].

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^[3]. 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^[4],[5].

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^[6]. Il est parfois appelé farthest first traversal^[7].

• 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^[7].

La complexité en temps de l'algorithme est O(nk)^[6].

Méthode du seuil

On peut obtenir une 2-approximation par la méthode du seuil (ou threshold method^[8] aussi appelé parametric pruning^[9],[10]). 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^[11].

Difficulté d'approximation

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

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^[13].

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^[5].

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^[1]), 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^[14], comme pour les k-moyennes.

Notes et références

1. La traduction en français provient de la traduction par Nicolas Shabanel de (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), voir « Algorithmes d'approximation : table des matières », sur le site de Nicolas Schabanel.
2. Samir Khuller et Yoram J. Sussmann, « The Capacitated \emph{K}-Center Problem », SIAM J. Discrete Math., vol. 13, n^o 3,‎ 2000, p. 403-418
3. Dorit S Hochbaum, « Various notions of approximations: Good, better, best, and more », dans Approximation algorithms for NP-hard problems, PWS Publishing Co., 1996, p. 346-446
4. (en) Michael Garey et David S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979 (ISBN 0-7167-1045-5).
5. (en) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski et Gerhard Woeginger, « Metric k-center », sur A compendium of NP optimization problems, 2000.
6. Teofilo F. Gonzalez, « Clustering to minimize the maximum intercluster distance », Theoretical Computer Science, vol. 38,‎ 1985, p. 293-306 (DOI 10.1016/0304-3975(85)90224-5)
7. (en) Sanjoy Dasgupta, « Lecture 1 : Clustering in metric spaces », sur Université de Californie à San Diego, 2013
8. Jack Edmonds et Delbert Ray Fulkerson, « Bottleneck extrema », Journal of Combinatorial Theory, vol. 8, n^o 3,‎ 1970, p. 299-306.
9. (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 5 (« k-center »)
10. Voir slides 14-19 de Thomas Rothvoss, « Approximation Algorithm », 2009.
11. Dorit S. Hochbaum et David B. Shmoys, « A Best Possible Heuristic for the k-Center Problem », Mathematics of Operations Research, vol. 10, n^o 2,‎ 1985, p. 180-184
12. Wen-Lian Hsu et George L. Nemhauser, « Easy and hard bottleneck location problems », Discrete Applied Mathematics, Elsevier, vol. 1, n^o 3,‎ 1979, p. 209-215
13. David Eisenstat, Philip N. Klein et Claire Mathieu, « Approximating k-center in planar graphs », dans Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, 2014, p. 617-627
14. David P. Williamson et David B. Shmoys, chap. 2.2 « The k-center problem », dans The Design of Approximation Algorithms, Cambridge University Press 

Liens externes

• (en) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski et Gerhard Woeginger, « Metric k-center », sur A compendium of NP optimization problems, 2000.
• (en) Sanjoy Dasgupta, « Lecture 1 : Clustering in metric spaces », sur Université de Californie à San Diego, 2013