Browsing by Author "Rubio Orellana, Benjamín Eduardo"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Identifying outbreaks in sewer networks: An adaptive sampling scheme under network's uncertainty
    (2024) Baboun Larach, José; Beaudry, Isabelle S.; Castro Cepero, Luis Mauricio; Gutiérrez González, Felipe Iván; Jara Vallejos, Alejandro Antonio; Rubio Orellana, Benjamín Eduardo; Verschae, José
    Motivated by the implementation of a SARS-Cov-2 sewer surveillance system in Chile during the COVID-19 pandemic, we propose a set of mathematical and algorithmic tools that aim to identify the location of an outbreak under uncertainty in the network structure. Given an upper bound on the number of samples we can take on any given day, our framework allows us to detect an unknown infected node by adaptively sampling different network nodes on different days. Crucially, despite the uncertainty of the network, the method allows univocal detection of the infected node, albeit at an extra cost in time. This framework relies on a specific and well-chosen strategy that defines new nodes to test sequentially, with a heuristic that balances the granularity of the information obtained from the samples. We extensively tested our model in real and synthetic networks, showing that the uncertainty of the underlying graph only incurs a limited increase in the number of iterations, indicating that the methodology is applicable in practice.
  • Thumbnail Image
    Item
    Searching for infections: algorithms for multiple sampling on trees and planar graphs
    (2023) Rubio Orellana, Benjamín Eduardo; Verschae, José; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    En el contexto de la pandemia de COVID-19, la capacidad de detectar y rastrear la propagacion del virus se ha vuelto esencial para implementar políticas preventivas efectivas. Con este fin, la epidemiología basada en aguas residuales ha sido estudiada recientemente en forma de pruebas de PCR en muestras de aguas residuales, produciendo resultados prometedores en el monitoreo del estado y las concentraciones de carga viral dentro de diferentes comunidades. En esta tesis, formulamos el problema de encontrar nuevas fuentes de infeccion como un problema de búsqueda en un grafo dirigido que representa la red de aguas residuales. Comenzamos modelando formalmente el problema de encontrar estrategias óptimas que minimicen el número máximo de pasos necesarios para encontrar la fuente de una infección en el peor de los casos. Suponiendo una estructura de árbol en el grafo, obtenemos un algoritmo de tiempo O(K|V |) para encontrar estrategias óptimas que tomen como máximo K muestras diarias. Además, inspirados en escenarios reales, analizamos el problema de trabajar con una representación incierta de la red y obtenemos cotas superiores e inferiores para el número máximo de pasos necesarios por una estrategia óptima en diferentes clases de grafos en este entorno. Específicamente, logramos demostrar una cota superior de O((! + ) log |V |) para grafos con un ancho de árbol de como máximo ! y un grado de entrada , y una cercana cota inferior de ⌦(p|V |) para grafos planares. Además, presentamos una heurística codiciosa para muestrear en grafos inciertos. Todos los algoritmos fueron probados usando datos reales obtenidos de la red de aguas residuales de San Pedro de la Paz, Chile. Las simulaciones realizadas muestran que utilizando 5 y 10 muestras diarias, el enfoque heurístico necesita como máximo 18 y 10 pasos respectivamente, y en promedio 8.65 y 5.34 pasos. Esto muestra que es teóricamente posible aplicar las estrategias desarrolladas para encontrar fuentes de infección en redes de tamaño real en tiempo razonable, incluso al trabajar con incertidumbre en el sistema.