An optimal algorithm for strict circular seriation
Loading...
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2021