Problema de 1 centro

El problema del centro único , también conocido como problema minimax o problema de localización minmax , es un problema clásico de optimización combinatoria en la investigación operativa del tipo de localización de instalaciones . En su caso más general, el problema se plantea de la siguiente manera: dado un conjunto de n puntos de demanda, un espacio de localizaciones factibles para una instalación y una función para calcular el coste de transporte entre una instalación y cualquier punto de demanda, encontrar una localización de la instalación que minimice el coste máximo de transporte entre la instalación y el punto de demanda.

Existen numerosos casos particulares del problema, dependiendo de la elección de la ubicación tanto de los puntos de demanda como de las instalaciones, así como de la función de distancia.

Un caso especial simple es cuando las ubicaciones factibles y los puntos de demanda están en el plano con distancia euclidiana como costo de transporte ( problema de ubicación de instalaciones euclidianas minmax planar, problema euclidiano de 1-centro en el plano, etc.). También se conoce como el problema del círculo más pequeño . Su generalización a espacios euclidianos n- dimensionales se conoce como el problema de la bola envolvente más pequeña . Una generalización adicional ( ubicación de instalaciones euclidianas ponderadas ) es cuando el conjunto de pesos se asigna a los puntos de demanda y el costo de transporte es la suma de los productos de las distancias por los pesos correspondientes. Otro caso especial, el problema de la cadena más cercana , surge cuando las entradas son cadenas y su distancia se mide usando la distancia de Hamming .

El problema del centro único se puede reformular como encontrar una estrella en un grafo completo ponderado que minimice el peso máximo de las aristas seleccionadas. El problema correspondiente de minimizar el peso máximo de un camino entre dos vértices seleccionados, en lugar de una estrella, se denomina problema del camino minimax .

• Árbol de diámetro mínimo que abarca
• Localización de instalaciones Minsum ( problema de la 1-mediana ), siendo la mediana geométrica un caso especial.
• Ubicación de la instalación Maxmin ( ubicación de la instalación desagradable )
• problema del centro k
• problema de k-medianas

• Megiddo, Nimrod (noviembre de 1983). "El problema euclidiano ponderado de 1 centro" (PDF) . Matemáticas de la investigación operativa . 8 (4): 498– 504. doi : 10.1287/moor.8.4.498 .
• Foul, Abdelaziz (mayo de 2006). "Un problema de un centro en el plano con puntos de demanda distribuidos uniformemente". Operations Research Letters . 34 (3). Elsevier: 264–268 . doi : 10.1016/j.orl.2005.04.011 .
• Chandrasekaran, R. (julio de 1982). "El problema euclidiano ponderado de 1 centro". Operations Research Letters . 1 (3). Elsevier: 111– 112. doi : 10.1016/0167-6377(82)90009-8 .
• Colebrook, M.; J. Gutiérrez, S. Alonso; J. Sicilia (diciembre de 2002). "Un nuevo algoritmo para el problema indeseable del centro único en redes". Journal of the Operational Research Society . 53 (12). Palgrave Macmillan Journals: 1357–1366 . doi : 10.1057/palgrave.jors.2601468 . JSTOR 822725 . 
• Burkard, Rainer E.; Helidon Dollani (febrero de 2002). "Una nota sobre el problema robusto de 1 centro en árboles". Annals of Operations Research . 110 ( 1–4 ). Kluwer Academic Publishers: 69–82 . doi : 10.1023/A:1020711416254 . ISSN 1572-9338 .