Centro k métrico

---

En teoría de grafos , el problema de ubicación de instalaciones métricas o centro k métrico es un problema de optimización combinatoria estudiado en informática teórica . Dadas n ciudades con distancias específicas, uno quiere construir k almacenes en diferentes ciudades y minimizar la distancia máxima de una ciudad a un almacén. En la teoría de grafos, esto significa encontrar un conjunto de k vértices para los cuales la mayor distancia de cualquier punto a su vértice más cercano en el conjunto k sea ​​mínima. Los vértices deben estar en un espacio métrico, proporcionando un gráfico completo que satisfaga eldesigualdad triangular .

Sea un espacio métrico donde es un conjunto y es una métrica Un conjunto , se proporciona junto con un parámetro . El objetivo es encontrar un subconjunto tal que la distancia máxima de un punto al punto más cercano se minimice. El problema se puede definir formalmente de la siguiente manera: Para un espacio métrico ( ,d),${\ estilo de visualización (X, d)}$${\ estilo de visualización X}$${\ estilo de visualización d}$
${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}$${\ estilo de visualización k}$${\displaystyle {\mathcal {C}}\subseteq \mathbf {V} }$${\displaystyle |{\mathcal {C}}|=k}$${\ estilo de visualización \ mathbf {V}}$${\displaystyle {\mathcal {C}}}$
${\displaystyle {\mathcal {X}}}$

Es decir, cada punto en un grupo está a una distancia máxima de su centro respectivo. ^[1]${\displaystyle r^{\mathcal {C}}(V)}$

El problema de agrupamiento de centros k también se puede definir en un gráfico no dirigido completo G  = ( V ,  E ) de la siguiente manera:
Dado un gráfico no dirigido completo G  = ( V ,  E ) con distancias d ( v _i ,  v _j ) ∈  N que satisfacen la desigualdad del triángulo, encuentre un subconjunto C  ⊆  V con | C | =  k mientras se minimiza:

En un grafo no dirigido completo G  = ( V ,  E ), si ordenamos las aristas en orden no decreciente de las distancias: d ( e ₁ ) ≤  d ( e ₂ ) ≤ … ≤  d ( e _m ) y sea G _i  = ( V,  E _i ), donde E _i  = { e ₁ ,  e ₂ , …,  e _i }. El problema del k -centro es equivalente a encontrar el índice i más pequeño tal que G _itiene un conjunto dominante de tamaño como máximo k .^[2]

Aunque el conjunto dominante es NP-completo , el problema del centro k sigue siendo NP-difícil . Esto es claro, ya que la optimalidad de una solución factible dada para el problema del k -centro puede determinarse a través de la reducción del conjunto dominante solo si conocemos en primer lugar el tamaño de la solución óptima (es decir, el índice i más pequeño tal que G _i tiene un conjunto dominante de tamaño a lo sumo k ), que es precisamente el núcleo difícil de los problemas NP-Hard .

---