Complexity, lower bounds, and algorithms for searching infected nodes in uncertain trees
Loading...
Date
2023
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2023
Keywords
Optimización combinatorial, Estrategias de búsqueda, Testeo grupal, Treewidth, NP-Completitud