Metric k-center

rdf:langString K-centre

rdf:langString 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).