Dublin Core
Title
An optimal algorithm for strict circular seriation
Subject
005.13
Ciencias de la computación
Algoritmos computacionales
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2021
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.
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.
Creator
Armstrong Cruz, Santiago
Date
2021-03-22T11:17:47Z
2021-03-22T11:17:47Z
2021
Contributor
Guzmán Paredes, Cristóbal
Sing-Long C., Carlos A.
Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Rights
acceso abierto
Format
x, 38, 26 páginas
application/pdf
Language
en
Type
tesis de maestría
Identifier
10.7764/tesisUC/ING/52746
https://doi.org/10.7764/tesisUC/ING/52746
https://repositorio.uc.cl/handle/11534/52746