Examinando por Autor "Jiménez, Andrea"

Mostrando 1 - 2 de 2
  • Miniatura
    Ítem
    Estudio de algoritmos óptimos y aproximados para el Problema de Localización Dinámica en grafos
    (Universidad de Valparaíso, 2025-08-12) Zamora Canales, Aline Valentina; Jiménez, Andrea
    En este trabajo se estudia el Problema de Localización Dinámica (PLD) en grafos, formulado por Chung, Graham y Saks [CGS89] en el año 1989. El Problema de Localización Dinámica es un problema de optimización combinatoria enmarcado dentro de las matemáticas discretas, que tiene como sistema un grafo G = (V,E) en donde una fuente ubicada en una cierta posici´on inicial en alg ´un v´ ertice de G, tiene la habilidad de desplazarse con el objetivo de resolver secuencialmente una lista de requerimientos ubicados en los v´ ertices del grafo minimizando el costo de desplazarse y resolverlos. Estudiamos dos escenarios: el Off-line, en donde la lista de requerimientos por resolver está totalmente disponible desde un inicio, y el On-line, en donde la lista de requerimientos por resolver se va revelando progresivamente y cada desplazamiento de la fuente se debe decidir con información parcial del futuro. En el contexto Offline estudiamos propiedades estructurales fundamentales que describen el comportamiento del óptimo para el PLD y diseñamos un algoritmo óptimo, basado en el paradigma de diseño de algoritmos conocido como programación dinámica. Justificamos teóricamente la correctitud de este algoritmo y calculamos la complejidad temporal, resultando en O(n2k), en donde n es la cantidad de vértices del grafo del sistema, y k es la cantidad de requerimientos por resolver. Implementamos este algoritmo en el lenguaje de programaci´on Python para utilizarlo como referencia para comparar el desempeño de algoritmos On-line. En el caso On-line, siguiendo el trabajo de Chung, Graham y Saks [CGS87, CGS89], introducimos un parámetro en grafos llamado Window Index (Windex), que mide el menor valor de ventana k para el cual existe un algoritmo óptimo para el PLD en G que trabaje tan solo conociendo los siguientes k requerimientos por resolver, es decir, el Windex esencialmente mide que tanta información necesito conocer del futuro para asegurar la existencia de un algoritmo que encuentre soluciones óptimas. Estudiamos grafos con Windex finito e infinito a partir del cálculo del Windex de clases particulares de grafos. Por otro lado, analizamos la correctitud y complejidad computacional de dos algoritmos: Algoritmo Glotón (de ventana 1) que en su diseño se utiliza el paradigma codicioso y garantiza un radio de aproximación 2 para el PLD en cualquier grafo. Algoritmo Windex 2 (de ventana 2) que es óptimo para grafos de Windex 2, y sustenta su diseño en la Propiedad de Tripleta de Steiner Única (USTP). Basándonos en la caracterización de Chung, Graham y Saks [CGS87], probamos que los grafos con Windex 2 son exactamente los grafos medianos, lo que incluye estructuras como árboles, grillas cuadradas e hipercubos. Para finalizar, realizamos una parte experimental en donde evaluamos el desempeño del Algoritmo Glotón y del Algoritmo Windex 2 en diferentes grafos, sustentando nuestra elección en el Windex de los grafos seleccionados y variando la densidad de las aristas de los grafos. Las implementaciones de los algoritmos las desarrollamos en el lenguaje de programación Python. En el caso del Algoritmo Windex 2, nuestros resultados dan evidencia empırica para la conjetura hecha por Chung, Graham y Saks [CGS89] acerca de la existencia de un algoritmo con ventana 2 y radio de aproximación 3/2. Por otro lado, a partir de los experimentos realizados, podemos decir que el Algoritmo Windex 2 supera consistentemente al Algoritmo Glotón, especialmente en grafos con Windex 2 o grafos con alta densidad, y que la estructura y densidad del grafo tienen un impacto directo en el desempeño de los algoritmos.
  • Miniatura
    Ítem
    Polynomial degeneracy for the first m energy levels of the antiferromagnetic Ising model
    (European Mathematical Society, 2021) Jiménez, Andrea
    In this work, we continue our investigation on the antiferromagnetic Ising model on triangulations of closed Riemann surfaces. On the one hand, according to R. Moessner and A. P. Ramirez [11], the antiferromagnetic Ising model on triangulations exhibits geometrical frustration, a well-studied concept in condensed matter physics. Typical geometrically frustrated systems present an exponential ground state degeneracy. On the other hand, the dual graph of a triangulation of a closed Riemann surface is a cubic graph. Cubic bridgeless graphs have exponentially many perfect matchings [3, 5], which implies in the case of planar triangulations, an exponential ground state degeneracy. However, this phenomenon does not persist for triangulations of higher genus surfaces. A possible explanation for a geometrically frustrated system with a low ground state degeneracy is that exponentially many states exist at a low energy level. In this work, we constructively show that this explanation does not match with the behavior of all triangulations of closed Riemann surfaces. To be more specific, for each integer m \geq 1m≥1, we construct a collection of triangulations \{T_n\}_{n > N(m)}{Tn} n>N(m) of a fixed closed Riemann surface with the property that the degeneracy of each of the first mm energy levels of T_nTn is a polynomial in the order nn of T_nTn.