Problema del centro k del vértice

El problema del vértice k -centro es un problema NP-duro clásico en informática . Tiene aplicación en la ubicación y agrupación de instalaciones . ^[1]^[2] Básicamente, el problema del vértice k -centro modela el siguiente problema real: dada una ciudad con instalaciones, encontrar las mejores instalaciones donde construir estaciones de bomberos. Dado que los bomberos deben atender cualquier emergencia lo más rápido posible, la distancia desde la instalación más lejana hasta la estación de bomberos más cercana debe ser lo más pequeña posible. En otras palabras, la posición de las estaciones de bomberos debe ser tal que todos los posibles incendios sean atendidos con la mayor rapidez posible. ${\ Displaystyle n}$ ${\ Displaystyle k}$

El problema del vértice k -centro es un problema NP-Hard clásico en informática . Fue propuesto por primera vez por Hakimi en 1964. ^[3] Formalmente, el problema del vértice k -centro consiste en: dado un gráfico completo no dirigido en un espacio métrico , y un entero positivo , encontrar un subconjunto tal que y la función objetivo se minimice. La distancia se define como la distancia desde el vértice hasta su centro más cercano en . ${\ Displaystyle G = (V, E)}$ ${\ Displaystyle k}$ ${\ Displaystyle C \ subseteq V}$ ${\ Displaystyle | C | \ leq k}$ ${\ Displaystyle r (C) = \ max _ {v \ in V} \ {d (v, C) \}}$ ${\ Displaystyle d (v, C)}$ ${\ Displaystyle v}$ ${\ Displaystyle C}$

Si , el problema del vértice k -centro no se puede resolver (óptimamente) en tiempo polinomial. Sin embargo, existen algunos algoritmos de tiempo polinomial que se acercan a las soluciones óptimas. Específicamente, 2 soluciones aproximadas . En realidad, si la mejor solución posible que puede lograrse mediante un algoritmo de tiempo polinomial es una aproximada a 2. ^[4]^[5]^[6]^[7] En el contexto de un problema de minimización, como el problema del vértice k -centro, una solución 2-aproximada es cualquier solución tal que , donde ${\ Displaystyle P \ neq NP}$ ${\ Displaystyle P \ neq NP}$ ${\ Displaystyle C '}$ ${\ Displaystyle r (C ') \ leq 2 \ times r ({\ text {OPT}})}$ ${\ Displaystyle r ({\ text {OPT}})}$ es del tamaño de una solución óptima. Un algoritmo que garantiza generar 2 soluciones aproximadas se conoce como algoritmo de 2 aproximaciones. Los principales algoritmos 2-aproximados para el problema del vértice k -centro reportados en la literatura son el algoritmo Sh, ^[8] el algoritmo HS, ^[7] y el algoritmo Gon. ^[5]^[6] Aunque estos algoritmos son los mejores (polinomiales) posibles, su rendimiento en la mayoría de los conjuntos de datos de referencia es muy deficiente. Debido a esto, se han desarrollado muchas heurísticas y metaheurísticas a lo largo del tiempo. Al contrario del sentido común, una de las heurísticas (polinomiales) más prácticas para el vértice k-El problema del centro se basa en el algoritmo CDS, que es un algoritmo de 3 aproximaciones ^[9]