Browsing by Author "Armstrong Cruz, Santiago"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    An optimal algorithm for strict circular seriation
    (2021) Armstrong Cruz, Santiago; Guzmán Paredes, Cristóbal; Sing-Long C., Carlos A.; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    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.