Centro k métrico

Problema de optimización combinatoria

En teoría de grafos , el problema del centro k de la métrica o problema del centro k del vértice es un problema de optimización combinatoria clásico estudiado en informática teórica que es NP-hard . Dadas n ciudades con distancias específicas, 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 sea mínima. Los vértices deben estar en un espacio métrico , proporcionando un grafo completo que satisface la desigualdad triangular . Tiene aplicación en la ubicación y agrupamiento de instalaciones . ^{[1] [2]}

Definición formal

El problema fue propuesto por primera vez por Hakimi en 1964. ^[3]

Sea un espacio métrico donde es un conjunto y es una métrica Se proporciona un conjunto , 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 sea mínima. 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 coste d(v, ) ${\displaystyle r^{\mathcal {C}}(\mathbf {V} )={\underset {v\in V}{\max }}}$ ${\displaystyle {\mathcal {C}}}$

Es decir, cada punto de un cúmulo se encuentra a una distancia máxima de su respectivo centro. ^[4] ${\displaystyle r^{\mathcal {C}}(V)}$

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

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

Complejidad computacional

En un grafo 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 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 _i tenga un conjunto dominante de tamaño como máximo k . ^[5]

Aunque el Conjunto Dominante es NP-completo , el problema del k -centro sigue siendo NP-duro . 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 como máximo k ), que es precisamente el núcleo difícil de los problemas NP-Duro . Aunque una reducción de Turing puede evitar este problema probando todos los valores de k .

Aproximaciones

Un algoritmo simple y codicioso

Un algoritmo de aproximación voraz simple que logra un factor de aproximación de 2 se construye utilizando un recorrido de más lejos 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: ${\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}}$
• Seleccione el punto con mayor distancia desde . ${\displaystyle {\bar {c}}_{2}}$ ${\displaystyle {\bar {c}}_{1}}$
• Añádalo al conjunto de centros y denote este conjunto expandido de centros como . Continúe con esto hasta que se encuentren k centros. ${\displaystyle C_{2}}$

Duración del programa

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

Demostrando el factor de aproximación

La solución obtenida mediante el algoritmo voraz simple es una aproximación de 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 voraz de K -centros calcula un conjunto K de k centros, tal que K es una 2-aproximación al agrupamiento óptimo de k -centros de V . ${\displaystyle \mathbf {V} \subseteq {\mathcal {X}}}$ ${\displaystyle {\mathcal {X}}}$

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

Este teorema se puede demostrar utilizando dos casos como los siguientes:

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

• Consideremos 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 lo 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 triangular: ${\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 (por el principio del palomar, 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 añadió posteriormente al conjunto central mediante el algoritmo codicioso, digamos en la i ^-ésima 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 que 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}}}$^[4]

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 , buscando el índice más pequeño i que tiene un conjunto independiente máximo con un tamaño de al menos k . ^[7] 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. ^[8] Además, las distancias de todos los bordes en G deben satisfacer la desigualdad triangular si el problema del k -centro se va a aproximar dentro de cualquier factor constante, a menos que P = NP. ^[9]

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. ^[10] Esto también es cierto cuando se parametriza por la dimensión de duplicación (de hecho, la dimensión de una métrica de Manhattan ), a menos que P=NP . ^[11] Cuando se considera el parámetro combinado dado por k y la dimensión de duplicación , el k -Centro sigue siendo W[1]-difícil pero es posible obtener un esquema de aproximación parametrizado . ^[12] Esto es incluso posible para la variante con capacidades de vértice, que limitan la cantidad de vértices que se pueden asignar a un centro abierto de la solución. ^[13]

Algoritmos de aproximación

Si , el problema del vértice k -centro no puede ser resuelto (óptimamente) en tiempo polinomial. Sin embargo, hay algunos algoritmos de aproximación en tiempo polinomial que obtienen soluciones casi óptimas. Específicamente, soluciones 2-aproximadas . En realidad, si la mejor solución posible que puede ser lograda por un algoritmo de tiempo polinomial es una 2-aproximada. ^{[14] [15] [16] [17]} En el contexto de un problema de minimización, tal como el problema del vértice k -centro, una solución 2-aproximada es cualquier solución tal que , donde es el tamaño de una solución óptima. Un algoritmo que garantiza generar soluciones 2-aproximadas es conocido como un algoritmo 2-aproximado. Los principales algoritmos 2-aproximados para el problema del vértice k -centro reportados en la literatura son el algoritmo Sh, ^[18] el algoritmo HS, ^[17] y el algoritmo Gon. ^{[15] [16]} Aunque estos algoritmos son los mejores (polinómicos) 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. Contrariamente al sentido común, una de las heurísticas (polinómicas) más prácticas para el problema del vértice k -centro se basa en el algoritmo CDS, que es un algoritmo de 3 aproximaciones ^[19] ${\displaystyle P\neq NP}$ ${\displaystyle P\neq NP}$ ${\displaystyle C'}$ ${\displaystyle r(C')\leq 2\times r({\text{OPT}})}$ ${\displaystyle r({\text{OPT}})}$

El algoritmo Sh

Formalmente caracterizado por David Shmoys en 1995, ^[18] el algoritmo Sh toma como entrada un grafo completo no dirigido , un entero positivo y una suposición sobre cuál es el tamaño óptimo de la solución. El algoritmo Sh funciona de la siguiente manera: selecciona el primer centro al azar. Hasta ahora, la solución consta de un solo vértice, . A continuación, selecciona el centro al azar del conjunto que contiene todos los vértices cuya distancia desde es mayor que . En este punto, . Finalmente, selecciona los centros restantes de la misma manera que fueron seleccionados. La complejidad del algoritmo Sh es , donde es el número de vértices. ${\displaystyle G=(V,E)}$ ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle c_{1}}$ ${\displaystyle C=\{c_{1}\}}$ ${\displaystyle c_{2}}$ ${\displaystyle C}$ ${\displaystyle 2\times r}$ ${\displaystyle C=\{c_{1},c_{2}\}}$ ${\displaystyle k-2}$ ${\displaystyle c_{2}}$ ${\displaystyle O(kn)}$ ${\displaystyle n}$

El algoritmo HS

Propuesto por Dorit Hochbaum y David Shmoys en 1985, el algoritmo HS toma como base el algoritmo Sh. ^[17] Al observar que el valor de debe ser igual al costo de alguna arista en , y dado que hay aristas en , el algoritmo HS básicamente repite el algoritmo Sh con cada costo de arista. La complejidad del algoritmo HS es . Sin embargo, al ejecutar una búsqueda binaria sobre el conjunto ordenado de costos de aristas, su complejidad se reduce a . ${\displaystyle r({\text{OPT}})}$ ${\displaystyle E}$ ${\displaystyle O(n^{2})}$ ${\displaystyle E}$ ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{2}\log n)}$

El algoritmo Gon

Propuesto independientemente por Teófilo González , ^[15] y por Martin Dyer y Alan Frieze ^[16] en 1985, el algoritmo Gon es básicamente una versión más poderosa del algoritmo Sh. Mientras que el algoritmo Sh requiere una suposición sobre , el algoritmo Gon prescinde de dicha suposición al notar que si existe un conjunto de vértices a una distancia mayor que , entonces el vértice más alejado debe estar dentro de dicho conjunto. Por lo tanto, en lugar de calcular en cada iteración el conjunto de vértices a una distancia mayor que y luego seleccionar un vértice aleatorio, el algoritmo Gon simplemente selecciona el vértice más alejado de cada solución parcial . La complejidad del algoritmo Gon es , donde es el número de vértices. ${\displaystyle r}$ ${\displaystyle r({\text{OPT}})}$ ${\displaystyle 2\times r({\text{OPT}})}$ ${\displaystyle 2\times r}$ ${\displaystyle C'}$ ${\displaystyle O(kn)}$ ${\displaystyle n}$

El algoritmo CDS

Propuesto por García Díaz et al. en 2017, ^[19] el algoritmo CDS es un algoritmo de 3 aproximaciones que toma ideas del algoritmo Gon (heurística del punto más lejano), el algoritmo HS (poda paramétrica) y la relación entre el problema del vértice k -centro y el problema del Conjunto Dominante . El algoritmo CDS tiene una complejidad de . Sin embargo, al realizar una búsqueda binaria sobre el conjunto ordenado de costos de aristas, se propone una heurística más eficiente llamada CDSh. La complejidad del algoritmo CDSh es . A pesar del desempeño subóptimo del algoritmo CDS y el desempeño heurístico de CDSh, ambos presentan un desempeño mucho mejor que los algoritmos Sh, HS y Gon. ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{2}\log n)}$

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. ^[20] Esto también es cierto cuando se parametriza por la dimensión de duplicación (de hecho, la dimensión de una métrica de Manhattan ), a menos que P=NP . ^[21] Cuando se considera el parámetro combinado dado por k y la dimensión de duplicación , el k -Centro sigue siendo W[1]-difícil pero es posible obtener un esquema de aproximación parametrizado . ^[22] Esto es incluso posible para la variante con capacidades de vértice, que limitan la cantidad de vértices que se pueden asignar a un centro abierto de la solución. ^[23]

Comparación experimental

Algunos de los conjuntos de datos de referencia más utilizados para el problema del vértice k -centro son las instancias pmed de OR-Lib. ^[24] y algunas instancias de TSP-Lib. ^[25] La Tabla 1 muestra la media y la desviación estándar de los factores de aproximación experimentales de las soluciones generadas por cada algoritmo en las 40 instancias pmed de OR-Lib ^[19].

Heurística polinómica

Algoritmo puro codicioso

El algoritmo puro voraz (o Gr) sigue la idea central de los algoritmos voraces : tomar decisiones locales óptimas. En el caso del problema de k centros en el vértice, la decisión local óptima consiste en seleccionar cada centro de tal manera que el tamaño de la solución (radio de cobertura) sea mínimo en cada iteración. En otras palabras, el primer centro seleccionado es el que resuelve el problema de 1 centro. El segundo centro seleccionado es el que, junto con el centro anterior, genera una solución con un radio de cobertura mínimo. Los centros restantes se seleccionan de la misma manera. La complejidad del algoritmo Gr es . ^[26] El rendimiento empírico del algoritmo Gr es pobre en la mayoría de las instancias de referencia. ${\displaystyle O(kn^{2})}$

Algoritmo de puntuación

El algoritmo de puntuación (o Scr) fue introducido por Jurij Mihelič y Borut Robič en 2005. ^[27] Este algoritmo aprovecha la reducción del problema del vértice k -centro al problema del conjunto mínimo dominante. El problema se resuelve podando el gráfico de entrada con cada valor posible del tamaño de solución óptimo y luego resolviendo el problema del conjunto mínimo dominante heurísticamente. Esta heurística sigue el principio perezoso, que toma cada decisión lo más lenta posible (opuesto a la estrategia voraz). La complejidad del algoritmo Scr es . El rendimiento empírico del algoritmo Scr es muy bueno en la mayoría de las instancias de referencia. Sin embargo, su tiempo de ejecución rápidamente se vuelve impráctico a medida que aumenta la entrada. Por lo tanto, parece ser un buen algoritmo solo para instancias pequeñas. ${\displaystyle O(n^{4})}$

Véase también

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

Referencias

1. Pacheco, Joaquín A.; Casado, Silvia (diciembre de 2005). "Resolución de dos modelos de localización con pocas instalaciones mediante una heurística híbrida: un caso real de recursos sanitarios". Computers & Operations Research . 32 (12): 3075–3091. doi :10.1016/j.cor.2004.04.009. ISSN  0305-0548.
2. Kaveh, A.; Nasr, H. (agosto de 2011). "Resolución del problema del centro condicional e incondicional con búsqueda de armonía modificada: un estudio de caso real". Scientia Iranica . 18 (4): 867–877. doi : 10.1016/j.scient.2011.07.010 . ISSN  1026-3098.
3. Hakimi, SL (1964). "Ubicaciones óptimas de los centros de conmutación y los centros absolutos y las medianas de un gráfico". Investigación de operaciones . 12 (3): 450–459. doi :10.1287/opre.12.3.450. JSTOR  168125.
4. Har-peled, Sariel (2011). Algoritmos de aproximación geométrica . Boston, MA, EE. UU.: American Mathematical Society. ISBN 978-0821849118.
5. Vazirani, Vijay V. (2003), Algoritmos de aproximación , Berlín: Springer, págs. 47–48, ISBN 3-540-65367-8
6. Gonzalez, Teofilo F. (1985), "Agrupamiento para minimizar la distancia máxima entre clústeres", Theoretical Computer Science , vol. 38, Elsevier Science BV, pp. 293–306, doi : 10.1016/0304-3975(85)90224-5
7. Hochbaum, Dorit S. ; Shmoys, David B. (1986), "Un enfoque unificado para algoritmos de aproximación para problemas de cuello de botella", Journal of the ACM , vol. 33, págs. 533–550, doi :10.1145/5925.5933, ISSN  0004-5411, S2CID  17975253
8. 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
9. Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek ; Woeginger, Gerhard (2000), "Centro k mínimo", un compendio de problemas de optimización NP
10. Feldmann, Andreas Emil (1 de marzo de 2019). "Aproximaciones de parámetros fijos para problemas de k-centros en gráficos de baja dimensión de autopistas" (PDF) . Algorithmica . 81 (3): 1031–1052. doi :10.1007/s00453-018-0455-0. ISSN  1432-0541. S2CID  46886829.
11. Feder, Tomás; Greene, Daniel (1 de enero de 1988). "Algoritmos óptimos para agrupamiento aproximado". Actas del vigésimo simposio anual de la ACM sobre teoría de la computación - STOC '88 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 434–444. doi :10.1145/62212.62255. ISBN. 978-0-89791-264-8.S2CID658151  .​
12. Feldmann, Andreas Emil; Marx, Dániel (1 de julio de 2020). "La dureza parametrizada del problema de k-centros en redes de transporte" (PDF) . Algorithmica . 82 (7): 1989–2005. doi :10.1007/s00453-020-00683-w. ISSN  1432-0541. S2CID  3532236.
13. Feldmann, Andreas Emil; Vu, Tung Anh (2022). "Centro $$k$$ generalizado: distinción entre duplicación y dimensión de autopista". En Bekos, Michael A.; Kaufmann, Michael (eds.). Conceptos de teoría de grafos en informática . Apuntes de clase en informática. Vol. 13453. Cham: Springer International Publishing. págs. 215–229. arXiv : 2209.00675 . doi :10.1007/978-3-031-15914-5_16. ISBN 978-3-031-15914-5.
14. Kariv, O.; Hakimi, SL (diciembre de 1979). "Un enfoque algorítmico para los problemas de localización de redes. I: Los p-centros". Revista SIAM de Matemáticas Aplicadas . 37 (3): 513–538. doi :10.1137/0137040. ISSN  0036-1399.
15. Gonzalez, Teofilo F. (1985). "Agrupamiento para minimizar la distancia máxima entre clústeres". Ciencias Informáticas Teóricas . 38 : 293–306. doi : 10.1016/0304-3975(85)90224-5 . ISSN  0304-3975.
16. Dyer, ME; Frieze, AM (febrero de 1985). "Una heurística simple para el problema del p-centro". Operations Research Letters . 3 (6): 285–288. doi :10.1016/0167-6377(85)90002-1. ISSN  0167-6377.
17. Hochbaum, Dorit S. ; Shmoys, David B. (mayo de 1985). "La mejor heurística posible para el problema del centro k ". Matemáticas de la investigación de operaciones . 10 (2): 180–184. doi :10.1287/moor.10.2.180. ISSN  0364-765X.
18. Shmoys, David B. (1995). "Computing near-optimal solutions to combinatorial optimalization problems". Optimización combinatoria . Serie DIMACS en Matemática discreta y ciencia de la computación teórica. Vol. 20. págs. 355––397. CiteSeerX 10.1.1.33.1719 . doi :10.1090/dimacs/020/07. ISBN .  9780821802397.
19. Garcia-Diaz, Jesus; Sanchez-Hernandez, Jairo; Menchaca-Mendez, Ricardo; Menchaca-Mendez, Rolando (2017-07-01). "Cuando un factor de aproximación peor da un mejor rendimiento: un algoritmo de 3 aproximaciones para el problema del vértice k -centro". Journal of Heuristics . 23 (5): 349–366. doi :10.1007/s10732-017-9345-x. ISSN  1381-1231. S2CID  254500532.
20. Feldmann, Andreas Emil (1 de marzo de 2019). "Aproximaciones de parámetros fijos para problemas de k-centros en gráficos de baja dimensión de autopistas". Algorithmica . 81 (3): 1031–1052. arXiv : 1605.02530 . doi :10.1007/s00453-018-0455-0. ISSN  1432-0541. S2CID  46886829.
21. Feder, Tomás; Greene, Daniel (1 de enero de 1988). "Algoritmos óptimos para agrupamiento aproximado". Actas del vigésimo simposio anual de la ACM sobre teoría de la computación - STOC '88 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 434–444. doi :10.1145/62212.62255. ISBN. 978-0-89791-264-8.S2CID658151  .​
22. Feldmann, Andreas Emil; Marx, Dániel (1 de julio de 2020). "La dureza parametrizada del problema del centro k en redes de transporte". Algorithmica . 82 (7): 1989–2005. arXiv : 1802.08563 . doi :10.1007/s00453-020-00683-w. ISSN  1432-0541. S2CID  3532236.
23. Feldmann, Andreas Emil; Vu, Tung Anh (2022). "Centro $$k$$ generalizado: distinción entre duplicación y dimensión de autopista". En Bekos, Michael A.; Kaufmann, Michael (eds.). Conceptos de teoría de grafos en informática . Apuntes de clase en informática. Vol. 13453. Cham: Springer International Publishing. págs. 215–229. arXiv : 2209.00675 . doi :10.1007/978-3-031-15914-5_16. ISBN 978-3-031-15914-5.
24. Beasley, JE (1990). "OR-Library: distribución de problemas de prueba por correo electrónico". Revista de la Sociedad de Investigación Operativa . 41 (11): 1069–1072. doi :10.2307/2582903. JSTOR  2582903.
25. Reinelt, Gerhard (noviembre de 1991). "TSPLIB: una biblioteca de problemas del viajante de comercio". ORSA Journal on Computing . 3 (4): 376–384. doi :10.1287/ijoc.3.4.376. ISSN  0899-1499.
26. Rana, Rattan; Garg, Deepak (marzo de 2009). "Enfoques heurísticos para el problema del centro K". Conferencia Internacional de Computación Avanzada IEEE de 2009. IEEE. págs. 332–335. doi :10.1109/iadcc.2009.4809031. ISBN . 9781424429271.S2CID 12453616  .
27. Mihelič, Jurij; Robič, Borut (2005). "Resolución eficiente del problema del centro k con un algoritmo de conjunto dominante". Revista de informática y tecnología de la información . 13 (3): 225. CiteSeerX 10.1.1.205.3118 . doi : 10.2498/cit.2005.03.05 . ISSN  1330-1136. 

Lectura adicional

• Hochbaum, Dorit S. ; Shmoys, David B. (1985), "La mejor heurística posible para el problema de k-centros", Mathematics of Operations Research , vol. 10, págs. 180–184, doi :10.1287/moor.10.2.180