En teoría de grafos , el problema métrico k -centro o instalación métrica es un problema de optimización combinatoria estudiado en la informática teórica . Dadas n ciudades con distancias especificadas, se desea construir k almacenes en diferentes ciudades y minimizar la distancia máxima de una ciudad a un almacén. En teoría de grafos, esto significa encontrar un conjunto de k vértices para los cuales la distancia más grande de cualquier punto a su vértice más cercano en el conjunto k es mínima. Los vértices deben estar en un espacio métrico, proporcionando un gráfico completo que satisfaga eldesigualdad triangular .
Definicion formal
Dejar ser un espacio métrico donde es un conjunto y es un conjunto métrico
A, se proporciona junto con un parámetro . El objetivo es encontrar un subconjunto con tal que la distancia máxima de un punto en al punto más cercano en se minimiza. El problema se puede definir formalmente de la siguiente manera:
Para un espacio métrico (,D),
- Entrada: un conjunto y un parámetro .
- Salida: un conjunto de puntos.
- Objetivo: minimizar el costo d (v,)
Es decir, cada punto de un grupo está a una distancia como máximo de su respectivo centro. [1]
El problema de agrupamiento de k-centros también se puede definir en un gráfico completo no dirigido G = ( V , E ) de la siguiente manera:
Dado un gráfico completo no dirigido G = ( V , E ) con distancias d ( v i , v j ) ∈ N satisfactorio la desigualdad del triángulo, encuentre un subconjunto C ⊆ V con | C | = k minimizando:
Complejidad computacional
En un gráfico completo no dirigido G = ( V , E ), si ordenamos los bordes en orden no decreciente de las distancias: d ( e 1 ) ≤ d ( e 2 ) ≤… ≤ d ( e m ) y sea G i = ( V, E i ), donde E i = { e 1 , e 2 ,…, e i }. El problema del k -centro es equivalente a encontrar el índice más pequeño i tal que G i tenga un conjunto dominante de tamaño a lo sumo k . [2]
Aunque Dominating Set es NP-completo , el problema del k -centro sigue siendo NP-hard . Esto es claro, ya que la optimalidad de una solución factible dada para el problema de k -centros se puede determinar mediante la reducción del conjunto dominante solo si conocemos en primer lugar el tamaño de la solución óptima (es decir, el índice más pequeño i 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 .
Aproximaciones
Un simple algoritmo codicioso
Un simple algoritmo de aproximación codicioso que logra un factor de aproximación de 2 compilaciones.utilizando un recorrido más lejano primero en k iteraciones. Este algoritmo simplemente elige el punto más alejado del conjunto actual de centros en cada iteración como el nuevo centro. Puede describirse de la siguiente manera:
- Elige un punto arbitrario dentro
- Por cada punto calcular de
- Elige el punto con mayor distancia desde .
- Agréguelo al conjunto de centros y denote este conjunto ampliado de centros como . Continúe esto hasta que se encuentren k centros
Tiempo de ejecución
- La i- ésima iteración de elegir el i- ésimo centro toma hora.
- Hay k iteraciones de este tipo.
- Por lo tanto, en general, el algoritmo toma hora. [3]
Demostrar el factor de aproximación
La solución obtenida utilizando el algoritmo codicioso simple es una aproximación 2 a la solución óptima. Esta sección se centra en probar este factor de aproximación.
Dado un conjunto de n puntos, perteneciente a un espacio métrico (, d), el codicioso K -center algoritmo calcula un conjunto K de k centros, de manera que K es un 2-aproximación a la óptima k -center agrupación de V .
es decir [1]
Este teorema se puede probar usando dos casos como sigue,
Caso 1: Cada grupo de contiene exactamente un punto de
- Considere un punto
- Dejar ser el centro al que pertenece en
- Dejar ser el centro de que esta en
- Similar,
- Por la desigualdad del triángulo:
Caso 2: Hay dos centros y de que están ambos en , para algunos (Por el principio del casillero, esta es la única otra posibilidad)
- Supongamos, sin pérdida de generalidad, que se agregó más tarde al conjunto central por el algoritmo codicioso, digamos en i ésima iteración.
- Pero dado que el algoritmo codicioso siempre elige el punto más alejado del conjunto actual de centros, tenemos que y,
Otro algoritmo de aproximación de 2 factores
Otro algoritmo con el mismo factor de aproximación aprovecha el hecho de que el problema del k -centro es equivalente a encontrar el índice más pequeño i tal que G i tiene un conjunto dominante de tamaño como máximo k y calcula un conjunto independiente máximo de G i , mirando para el índice más pequeño i que tiene un conjunto independiente máximo con un tamaño de al menos k . [4] No es posible encontrar un algoritmo de aproximación con un factor de aproximación de 2 - ε para cualquier ε> 0, a menos que P = NP. [5] Además, las distancias de todas las aristas en G deben satisfacer la desigualdad del triángulo si el problema del k- centro debe aproximarse dentro de cualquier factor constante, a menos que P = NP. [6]
Ver también
Referencias
- ↑ a b c Har-peled, Sariel (2011). Algoritmos de aproximación geométrica . Boston, MA, EE.UU .: American Mathematical Society. ISBN 0821849115.
- ^ Vazirani, Vijay V. (2003), Algoritmos de aproximación , Berlín: Springer, págs. 47–48, ISBN 3-540-65367-8
- ^ González, Teófilo F. (1985), "Agrupación para minimizar la distancia máxima entre grupos", Informática teórica , 38 , Elsevier Science BV, págs. 293-306, doi : 10.1016 / 0304-3975 (85) 90224-5
- ^ Hochbaum, Dorit S .; Shmoys, David B. (1986), "Un enfoque unificado de algoritmos de aproximación para problemas de cuello de botella", Journal of the ACM , 33 , págs. 533–550, ISSN 0004-5411
- ^ Hochbaum, Dorit S. (1997), algoritmos de aproximación para problemas NP-Hard , Boston: PWS Publishing Company, págs. 346–398, ISBN 0-534-94968-1
- ^ Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek ; Woeginger, Gerhard (2000), "Centro k mínimo", Compendio de problemas de optimización de NP
Otras lecturas
- Hochbaum, Dorit S .; Shmoys, David B. (1985), "Una mejor heurística posible para el problema del centro k", Matemáticas de la investigación de operaciones , 10 , págs. 180-184