Registro en el INDIXE de Tesis Digitales de REMERI
ID
oai:tesis.ipn.mx:123456789/16123
TIPO
Tesis de Maestría
TÍTULO
Algoritmo de aproximación aleatorizado para el Problema de Selección de k Centros
AUTOR
García Díaz, Jesús.
ASESORES
Menchaca Méndez, Rolando.
INSTITUCIÓN
Instituto Politécnico Nacional (IPN)
FECHA
2016-02-09
PAIS
México
TEMAS
CIC.
DESCRIPCIÓN
El problema de selección de k-centros (k-center selection problem) consiste en, dado un grafo completo no dirigido G=(V,E) y un entero positivo k, determinar un conjunto de centros C ⊆ V, de cardinalidad menor o igual a k, tal que la máxima distancia de cada nodo hacia su centro más cercano sea mínima. A la máxima distancia obtenida se le denomina radio de cobertura r(C).
El problema de selección de k-centros ha sido ampliamente estudiado en áreas como Agrupamiento (Clustering) y Ubicación de Facilidades (Facility Location). Este problema cuenta con gran número de aplicaciones prácticas, tales como la distribución de inmuebles, de servicios de emergencia, de servicios en redes de computadoras, etcétera.
El problema de selección de k-centros es un problema que pertenece a la clase de complejidad NP-Difícil, lo cual implica que en caso de que P≠NP no puede ser resuelto de forma eficiente, es decir, en tiempo polinomial. De hecho, el único método conocido para resolver este problema de manera óptima es el de fuerza bruta, el cual consiste en comparar el radio de cobertura de todas las posibles soluciones y retornar aquella de tamaño mínimo. Este método se ejecuta en O(n^k) pasos, que es una cantidad de pasos exponencial con respecto a la variable k y por lo tanto no es considerado un método viable para instancias arbitrarias, en particular para valores grandes de k.
Es importante destacar que, de la misma manera que encontrar la solución óptima al problema de selección de k-centros es un problema NP-Difícil, encontrar una (2-ε)-aproximación, donde ε>0, también lo es. Esta cota de aproximación es estrecha, pues los mejores algoritmos polinomiales conocidos para resolver el problema de selección de k-centros encuentran soluciones con un factor de aproximación de 2 (es decir, entregan una 2-aproximación). Dado que no es posible diseñar mejores algoritmos polinomiales (a menos que P=NP), este tipo de problemas suelen ser abordados a través de enfoques muy diversos cuya finalidad es aproximarse tanto como sea posible a la solución óptima.
A la fecha se ha diseñado una gran cantidad de algoritmos para resolver el problema de selección de k-centros. Algunas de los técnicas utilizadas por estos algoritmos son las selecciones voraces (greedy), poda paramétrica, programación lineal, búsqueda tabú, búsqueda dispersa, etcétera. En la práctica los algoritmos que suelen entregar mejores resultados son aquellos clasificados como metaheurísticas. Desafortunadamente, este tipo de algoritmos, en general, no poseen una base teórica fuerte y por lo tanto no es posible caracterizar formalmente su complejidad o bien demostrar que encuentran soluciones buenas para instancias arbitrarias.
En esta tesis proponemos un nuevo algoritmo de aproximación aleatorizado de complejidad O(kn) para el problema de selección de k-centros. El algoritmo aleatorizado propuesto está basado en una nueva técnica que tiene por objetivo combinar las ventajas de los algoritmos de aproximación deterministas con las de los algoritmos aleatorizados amplificados. El algoritmo propuesto realiza una búsqueda aleatoria dentro del espacio de soluciones con base en el procedimiento seguido por un algoritmo de aproximación determinista. Una propiedad sobresaliente del algoritmo propuesto es que, en tiempo polinomial, encuentra una ρ-aproximación con una probabilidad caracterizable.
Demostramos que el algoritmo propuesto amplificado α veces entrega una ρ-aproximación con una probabilidad dependiente del valor de α, donde ρ es el factor de aproximación del algoritmo utilizado como base y α∈Z^+ es un parámetro de entrada del algoritmo propuesto definido por el usuario. Si bien la probabilidad de entregar una ρ -aproximación depende del valor de α, también es posible demostrar que esta probabilidad nunca será menor a 1-1/e.
Adicionalmente, se propone una variante de búsqueda local probabilística para el algoritmo propuesto. El esquema de nuestro método de búsqueda local consiste en examinar soluciones cercanas a la mejor solución actual. La relación de vencindad propuesta es también probabilística, en el sentido de que las soluciones examinadas son aquellas que resultan del muestreo de una distribución de probabilidad que es definida de tal manera que la mejor solución actual sea obtenida con una alta probabilidad. Los resultados experimentales obtenidos demuestran que no más de O(n^4) pasos son requeridos por el algoritmo propuesto para encontrar soluciones tan buenas como las entregadas por los mejores algoritmos polinomiales del estado del arte, encontrando incluso la mejor solución conocida en la mitad de las instancias de prueba utilizadas..