Searching for infections: algorithms for multiple sampling on trees and planar graphs
Loading...
Date
2023
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2023.
Keywords
Algoritmos, Búsqueda en grafos, Coronavirus, Grafos planares