An Optimal Algorithm for Strict Circular Seriation

摘要

The seriation problem seeks to order a sequence of n objects when the only information we are given is a dissimilarity matrix between all pairs of objects. In linear seriation the goal is to find a linear order of the objects in a manner that is consistent with their dissimilarity. For this problem optimal O(n2) algorithms are known. A generalization of the previous problem is circular seriation, where the goal is to find a circular order instead. In this thesis we study the circular seriation problem. Our contributions can be summarized as follows. First, we introduce circular Robinson matrices as the natural class of dissimilarity matrices for the circular seriation problem. Second, for the case of strict circular Robinson dissimilarity matrices we provide an optimal O(n2) algorithm for the circular seriation problem. Finally, we propose a statistical model to analyze the well-posedness of the circular seriation problem for large n. In particular, we establish O(log(n)/n) rates on the distance between any circular ordering found by solving the circular seriation problem to the underlying order of the model, in the Kendall-tau metric.