An optimal algorithm for strict circular seriation
| dc.contributor.advisor | Guzmán Paredes, Cristóbal | |
| dc.contributor.advisor | Sing-Long C., Carlos A. | |
| dc.contributor.author | Armstrong Cruz, Santiago | |
| dc.contributor.other | Pontificia Universidad Católica de Chile. Escuela de Ingeniería | |
| dc.date.accessioned | 2021-03-22T11:17:47Z | |
| dc.date.available | 2021-03-22T11:17:47Z | |
| dc.date.issued | 2021 | |
| dc.description | Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2021 | |
| dc.description.abstract | El problema de la seriación busca ordenar una secuencia de n objetos cuando la única información que se nos da es una matriz de disimilitud entre todos los pares de objetos. En la seriación lineal, el objetivo es encontrar un em orden lineal de los objetos manera que sea consistente con su disimilitud. Para este problema se conocen los algoritmos óptimos O(n2). Una generalización del problema anterior es seriación circular, donde el objetivo es encontrar un em orden circular. En esta tesis estudiamos el problema de la seriación circular. Nuestras contribuciones se pueden resumir de la siguiente manera. Primero, presentamos em matrices circulares de Robinson como la clase natural de matrices de disimilitud para el problema de seriación circular. En segundo lugar, para el caso de em matrices de disimilitud circular estrictas de Robinson proporcionamos un algoritmo O(n2) óptimo para el problema de seriación circular. Finalmente, proponemos un modelo estadístico para analizar el buen planteamiento (well-posedness en el sentido de Hadamard) del problema de seriación circular para grandes valores de n. En particular, establecemos tasas del orden O(log(n)/n) para la distancia entre cualquier orden circular encontrado al resolver el problema de seriación circular al orden subyacente del modelo, en la métrica de Kendall-tau. | |
| dc.format.extent | x, 38, 26 páginas | |
| dc.identifier.doi | 10.7764/tesisUC/ING/52746 | |
| dc.identifier.uri | https://doi.org/10.7764/tesisUC/ING/52746 | |
| dc.identifier.uri | https://repositorio.uc.cl/handle/11534/52746 | |
| dc.language.iso | en | |
| dc.nota.acceso | Contenido completo | |
| dc.rights | acceso abierto | |
| dc.subject.ddc | 005.13 | |
| dc.subject.dewey | Ciencias de la computación | es_ES |
| dc.subject.other | Algoritmos computacionales | es_ES |
| dc.title | An optimal algorithm for strict circular seriation | es_ES |
| dc.type | tesis de maestría | |
| sipa.codpersvinculados | 1041986 | |
| sipa.codpersvinculados | 126170 | |
| sipa.codpersvinculados | 232654 |