Dublin Core
Title
Searching for infections: algorithms for multiple sampling on trees and planar graphs
Subject
Algoritmos
Búsqueda en grafos
Coronavirus
Grafos planares
620
Ingeniería
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2023.
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.
Creator
Rubio Orellana, Benjamín Eduardo
Date
2023-11-08T19:07:56Z
2023-11-08T19:07:56Z
2023
Contributor
Verschae, José
Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Rights
acceso abierto
Format
x, 58 páginas
application/pdf
Language
en
Type
tesis de maestría
Identifier
10.7764/tesisUC/ING/75255
http://doi.org/10.7764/tesisUC/ING/75255
https://repositorio.uc.cl/handle/11534/75255