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

Simple item page
dc.catalogadorpva
dc.contributor.advisorVerschae, José
dc.contributor.authorBaboun Larach, José
dc.contributor.otherPontificia Universidad Católica de Chile. Escuela de Ingeniería
dc.date.accessioned2023-10-13T18:39:32Z
dc.date.available2023-10-13T18:39:32Z
dc.date.issued2023
dc.descriptionTesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2023
dc.description.abstractAbordamos 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.
dc.fechaingreso.objetodigital2023-10-13
dc.format.extentxiii, 87 páginas
dc.fuente.origenSRIA
dc.identifier.doi10.7764/tesisUC/ING/75114
dc.identifier.urihttps://doi.org/10.7764/tesisUC/ING/75114
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/75114
dc.information.autorucEscuela de ingeniería ; Verschae, José ; 0000-0002-2049-6467 ; 243006
dc.information.autorucEscuela de ingeniería ; Baboun Larach, José ; S/I ; 1045055
dc.language.isoen
dc.nota.accesoContenido completo
dc.rightsacceso abierto
dc.subjectOptimización combinatoriales_ES
dc.subjectEstrategias de búsquedaes_ES
dc.subjectTesteo grupales_ES
dc.subjectTreewidthes_ES
dc.subjectNP-Completitudes_ES
dc.subject.ddc620
dc.subject.deweyIngenieríaes_ES
dc.titleComplexity, lower bounds, and algorithms for searching infected nodes in uncertain treeses_ES
dc.typetesis de maestría
sipa.codpersvinculados243006
sipa.codpersvinculados1045055
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TESIS_JIBaboun_Firma Final.pdf
Size:
5.35 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.98 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
3.01 Tesis magíster