Complexity, lower bounds, and algorithms for searching infected nodes in uncertain trees

Complexity, lower bounds, and algorithms for searching infected nodes in uncertain trees

Optimización combinatorial

Estrategias de búsqueda

Testeo grupal

Treewidth

NP-Completitud

620

Ingeniería

Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2023

Abordamos el desafío de identificar nuevos brotes de COVID-19 a través de la red de aguas residuales de una ciudad. Es posible que tengamos información parcial de la red. En particular, una serie de tuberías no identificables que aparecen en los datos no transportan flujo en la realidad. Resolvemos el problema de encontrar nuevos brotes realizando una secuencia de consultas adaptativas en los nodos de un grafo acíclico dirigido, el cual modela la red. Una consulta determina si el nodo infectado envía agua contaminada a través del nodo consultado, asumiendo que el agua fluye a través de un árbol dirigido desconocido. Nuestro modelo es robusto ante cualquier realización del árbol. Mostramos que el problema es NP-difícil cuando se intenta minimizar el número de consultas en el peor caso. Luego presentamos algunas características de la solución óptima, incluyendo propiedades y cotas inferiores para los escenarios promedio y peor caso. Demostramos que el treewidth del grafo no es una cota inferior de la altura de la estrategia de búsqueda óptima. Para resolver el problema computacionalmente, presentamos tres algoritmos heurísticos. El Algoritmo de Entropía proporciona soluciones efectivas cercanas a la solución óptima para el caso sin incertidumbre. Sin embargo, su tiempo de ejecución puede ser exponencial en el número de diferentes caminos del grafo. El Algoritmo de Separación de Caminos retorna resultados ligeramente peores, pero se puede implementar en tiempo polinomial.
Finalmente, conectamos con el marco de Group Testing. Damos un algoritmo óptimo para el caso sin restricciones en el tamaño del conjunto a testear, así como una 5-aproximación para cuando este tamaño está acotado por el número separador del grafo multiplicado por el grado de entrada. Nuestros hallazgos tienen impacto en las áreas de Group Testing, investigación de operaciones, diseño de algoritmos y epidemiología en aguas residuales.

Baboun Larach, José

2023-10-13T18:39:32Z

2023-10-13T18:39:32Z

2023

Verschae, José

Pontificia Universidad Católica de Chile. Escuela de Ingeniería

acceso abierto

xiii, 87 páginas

application/pdf

en

tesis de maestría

10.7764/tesisUC/ING/75114

https://doi.org/10.7764/tesisUC/ING/75114

https://repositorio.uc.cl/handle/11534/75114