K-médiane

Le problème k-médiane, ou k-median 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 un magasin dans k villes, tel que la moyenne des distances entre les villes et leurs plus proches magasins soit minimisée. Ce problème, proche du problème des k-moyennes, permet entre autres de faire du partitionnement de données.

Une formalisation du problème est la suivante. Étant donné un ensemble de points V, de choisir un sous-ensemble de k points, appelés centres, tel que la moyenne des distances des points de V au plus proche centre soit minimisée. Le problème est le plus souvent exprimé dans un espace métrique. Il s'exprime alors naturellement comme un problème sur un graphe dont les arêtes ont des poids respectant l'inégalité triangulaire. On peut aussi considérer que les sommets sont divisés en deux catégories : les sommets ouvrables, et les sommets à couvrir.

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.

Définition formelle

Le problème s'exprime de la façon suivante.

É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: $\sum _{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}\sum _{v\in V}\min _{s\in S}d(v,s)$ .

Approximation

Le problème k-médiane est NP-difficile même dans le cas métrique. Il possède une assez large littérature pour l'approximation dans le cas métrique (le cas général n'est pas dans APX).

Plusieurs méthodes ont été utilisées, notamment l'optimisation linéaire[2] et la recherche locale[3].

Variantes, problèmes liés et applications

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-centre, 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'une k-médiane peut permettre de faire du partitionnement de données. Les distances représentent alors des similarités.

Notes et références

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.
Kamal Jain et Vijay Vazirani, « Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation, », Journal of the ACM (JACM), vol. 48, n^o 2,‎ 2001, p. 274-296
Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala et Vinayaka Pandit, « Local search heuristics for k-median and facility location problems », SIAM Journal on Computing, vol. 33, n^o 3,‎ 2004, p. 544-562

Liens externes

(en) Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski et Gerhard Woeginger, « Minimum k-median », sur A compendium of NP optimization problems, 2000.
David Dohan, Stefani Karp, Brian Matejek, « K-median Algorithms: Theory in Practice », sur Cours Advanced algorithms de Sanjeev Arora à l'université Stanford.

Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[schabanel-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] Kamal Jain et Vijay Vazirani, « Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation, », Journal of the ACM (JACM), vol. 48, n^o 2,‎ 2001, p. 274-296

[3] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala et Vinayaka Pandit, « Local search heuristics for k-median and facility location problems », SIAM Journal on Computing, vol. 33, n^o 3,‎ 2004, p. 544-562