Centro k métrico

Problema de optimización combinatoria

En teoría de grafos , el problema del centro k métrico es un problema de optimización combinatoria estudiado en informática teórica . Dadas n ciudades con distancias específicas, se quiere 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 k -conjunto sea mínima. Los vértices deben estar en un espacio métrico , proporcionando una gráfica completa que satisfaga la desigualdad del triángulo .

Definicion formal

Sea 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 tal que se minimice la distancia máxima de un punto al punto más cercano . El problema se puede definir formalmente de la siguiente manera: Para un espacio métrico ( ,d), ${\displaystyle (X,d)}$ ${\displaystyle X}$ ${\displaystyle d}$
${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}$ ${\displaystyle k}$ ${\displaystyle {\mathcal {C}}\subseteq \mathbf {V} }$ ${\displaystyle |{\mathcal {C}}|=k}$ ${\displaystyle \mathbf {V} }$ ${\displaystyle {\mathcal {C}}}$
${\displaystyle {\mathcal {X}}}$

• Entrada: un conjunto y un parámetro . ${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}$ ${\displaystyle k}$
• Salida: un conjunto de puntos. ${\displaystyle {\mathcal {C}}\subseteq \mathbf {V} }$ ${\displaystyle k}$
• Objetivo: Minimizar el costo d(v, ) ${\displaystyle r^{\mathcal {C}}(\mathbf {V} )={\underset {v\in V}{\max }}}$ ${\displaystyle {\mathcal {C}}}$

Es decir, cada punto de 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 satisfactorias la desigualdad del triángulo, encuentra un subconjunto C  ⊆  V con | C | =  k minimizando:

${\displaystyle \max _{v\in V}\min _{c\in C}d(v,c)}$

Complejidad computacional

En un gráfico completo no dirigido G  = ( V ,  E ), si ordenamos las aristas en orden no decreciente de las distancias: d ( e ₁ ) ≤  d ( e ₂ ) ≤ ... ≤  d ( e _m ) y dejamos GRAMO _yo  = (V,  mi _yo ), donde mi _yo  = { mi ₁ ,  mi ₂ , ...,  mi _yo }. 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 como máximo k .^[2]

Aunque el conjunto dominante es NP-completo , el problema del centro k sigue siendo NP-difícil . Esto está claro, ya que la optimización de una solución factible dada para el problema de k -centro puede determinarse mediante la reducción del conjunto dominante sólo 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 como máximo k ), que es precisamente el núcleo difícil de los problemas NP-Difíciles . Aunque una reducción de Turing puede solucionar este problema probando todos los valores de k .

Aproximaciones

Un algoritmo codicioso simple

Un algoritmo de aproximación codicioso simple que logra un factor de aproximación de 2 se construye 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 nuevo centro. Se puede describir de la siguiente manera: ${\displaystyle {\mathcal {C}}}$

• Elija un punto arbitrario en ${\displaystyle {\bar {c}}_{1}}$ ${\displaystyle C_{1}}$
• Para cada punto calcular desde ${\displaystyle v\in \mathbf {V} }$ ${\displaystyle d_{1}[v]}$ ${\displaystyle {\bar {c}}_{1}}$
• Elija el punto con mayor distancia desde . ${\displaystyle {\bar {c}}_{2}}$ ${\displaystyle {\bar {c}}_{1}}$
• Agréguelo al conjunto de centros y denote este conjunto ampliado de centros como . Continúe esto hasta que se encuentren k centros. ${\displaystyle C_{2}}$

Tiempo de ejecución

• La i- ^ésima iteración de elegir el i- ^ésimo centro lleva tiempo. ${\displaystyle {\mathcal {O}}(n)}$
• Hay k tales iteraciones.
• Por tanto, en general el algoritmo lleva tiempo. ^[3] ${\displaystyle {\mathcal {O}}(nk)}$

Demostrando 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 demostrar este factor de aproximación.

Dado un conjunto de n puntos , pertenecientes a un espacio métrico ( ,d), el algoritmo codicioso de K -centros calcula un conjunto K de k centros, tal que K es una aproximación 2 al agrupamiento óptimo de k -centros de V. ${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}$ ${\displaystyle {\mathcal {X}}}$

es decir ^[1] ${\displaystyle r^{\mathbf {K} }(\mathbf {V} )\leq 2r^{opt}(\mathbf {V} ,{\textit {k}})}$

Este teorema se puede demostrar utilizando dos casos de la siguiente manera,

Caso 1: Cada grupo de contiene exactamente un punto de ${\displaystyle {\mathcal {C}}_{opt}}$ ${\displaystyle \mathbf {K} }$

• Considere un punto ${\displaystyle v\in \mathbf {V} }$
• Sea el centro al que pertenece en ${\displaystyle {\bar {c}}}$ ${\displaystyle {\mathcal {C}}_{opt}}$
• Sea el centro de eso que está en ${\displaystyle {\bar {k}}}$ ${\displaystyle \mathbf {K} }$ ${\displaystyle \Pi ({\mathcal {C}}_{opt},{\bar {c}})}$
• ${\displaystyle d(v,{\bar {c}})=d(v,{\mathcal {C}}_{opt})\leq r^{opt}(\mathbf {V} ,k)}$
• Similarmente, ${\displaystyle d({\bar {k}},{\bar {c}})=d({\bar {k}},{\mathcal {C}}_{opt})\leq r^{opt}}$
• Por la desigualdad del triángulo: ${\displaystyle d(v,{\bar {k}})\leq d(v,{\bar {c}})+d({\bar {c}},{\bar {k}})\leq 2r^{opt}}$

Caso 2: Hay dos centros y ambos están en , para algunos (según el principio del casillero, esta es la única otra posibilidad) ${\displaystyle {\bar {k}}}$ ${\displaystyle {\bar {u}}}$ ${\displaystyle \mathbf {K} }$ ${\displaystyle \Pi ({\mathcal {C}}_{opt},{\bar {c}})}$ ${\displaystyle {\bar {c}}\in {\mathcal {C}}_{opt}}$

• Supongamos, sin pérdida de generalidad, que se agregó más tarde al centro establecido por el algoritmo codicioso, digamos en la i ^iteración . ${\displaystyle {\bar {u}}}$ ${\displaystyle \mathbf {K} }$
• Pero como el algoritmo codicioso siempre elige el punto más alejado del conjunto actual de centros, tenemos eso y, ${\displaystyle {\bar {k}}\in {\mathcal {C}}_{i-1}}$

${\displaystyle {\begin{aligned}r^{\mathbf {K} }(\mathbf {V} )\leq r^{{\mathcal {C}}_{i-1}}(\mathbf {V} )&=d({\bar {u}},{\mathcal {C}}_{i-1})\\&\leq d({\bar {u}},{\bar {k}})\\&\leq d({\bar {u}},{\bar {c}})+d({\bar {c}},{\bar {k}})\\&\leq 2r^{opt}\end{aligned}}}$^[1]

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 tenga un conjunto dominante de tamaño} k como máximo y calcula un conjunto máximo independiente de G _i , buscando 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 todos los bordes en G deben satisfacer la desigualdad del triángulo si el problema del centro k se va a aproximar dentro de cualquier factor constante, a menos que P = NP.^[6]

Aproximaciones parametrizadas

Se puede demostrar que el problema del k -Centro es W[2]-difícil de aproximar dentro de un factor de 2 − ε para cualquier ε > 0, cuando se usa k como parámetro. ^[7] Esto también es cierto cuando se parametriza mediante la dimensión de duplicación (de hecho, la dimensión de una métrica de Manhattan ), a menos que P=NP . ^[8] Al considerar el parámetro combinado dado por k y la dimensión de duplicación , k -Center sigue siendo W[1]-duro pero es posible obtener un esquema de aproximación parametrizado . ^[9] Esto es incluso posible para la variante con capacidades de vértice, que limita cuántos vértices se pueden asignar a un centro abierto de la solución. ^[10]

Ver también

• Problema del vendedor ambulante
• Corte k mínimo
• Conjunto dominante
• Conjunto independiente (teoría de grafos)
• Problema de ubicación de las instalaciones

Referencias

1. Har-peled, Sariel (2011). Algoritmos de aproximación geométrica . Boston, MA, EE.UU.: Sociedad Matemática Estadounidense. ISBN 978-0821849118.
2. Vazirani, Vijay V. (2003), Algoritmos de aproximación , Berlín: Springer, págs. 47–48, ISBN 3-540-65367-8
3. González, Teófilo F. (1985), "Agrupación para minimizar la distancia máxima entre grupos", Informática Teórica , vol. 38, Elsevier Science BV, págs. 293–306, doi : 10.1016/0304-3975(85)90224-5
4. Hochbaum, Dorit S .; Shmoys, David B. (1986), "Un enfoque unificado para algoritmos de aproximación para problemas de cuellos de botella", Journal of the ACM , vol. 33, págs. 533–550, doi :10.1145/5925.5933, ISSN  0004-5411, S2CID  17975253
5. Hochbaum, Dorit S. (1997), Algoritmos de aproximación para problemas NP-difíciles , Boston: PWS Publishing Company, págs. 346–398, ISBN 0-534-94968-1
6. Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek ; Woeginger, Gerhard (2000), "Centro k mínimo", Compendio de problemas de optimización NP
7. Feldmann, Andreas Emil (1 de marzo de 2019). "Aproximaciones de parámetros fijos para problemas de k-centro en gráficos de dimensiones de carreteras bajas" (PDF) . Algorítmica . 81 (3): 1031-1052. doi :10.1007/s00453-018-0455-0. ISSN  1432-0541. S2CID  46886829.
8. Feder, Tomás; Greene, Daniel (1 de enero de 1988). "Algoritmos óptimos para agrupamiento aproximado". Actas del vigésimo simposio anual de ACM sobre teoría de la informática - STOC '88 . Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 434–444. doi :10.1145/62212.62255. ISBN 978-0-89791-264-8. S2CID  658151.
9. Feldmann, Andreas Emil; Marx, Daniel (01-07-2020). "La dureza parametrizada del problema del centro k en las redes de transporte" (PDF) . Algorítmica . 82 (7): 1989-2005. doi :10.1007/s00453-020-00683-w. ISSN  1432-0541. S2CID  3532236.
10. Feldmann, Andreas Emil; Vu, Tung Anh (2022). "Centro $$k$$ generalizado: distinguir entre duplicación y dimensión de la carretera". En Bekos, Michael A.; Kaufmann, Michael (eds.). Conceptos de teoría de grafos en informática . Apuntes de conferencias sobre informática. vol. 13453. Cham: Editorial Internacional Springer. págs. 215-229. arXiv : 2209.00675 . doi :10.1007/978-3-031-15914-5_16. ISBN 978-3-031-15914-5.

Otras lecturas

• Hochbaum, Dorit S .; Shmoys, David B. (1985), "La mejor heurística posible para el problema del centro k", Matemáticas de la investigación de operaciones , vol. 10, págs. 180–184, doi :10.1287/moor.10.2.180