Seriation in the Presence of Errors: A Factor 16 Approximation Algorithm for l (a)-Fitting Robinson Structures to Distances
The classical seriation problem consists in finding a permutation of the rows and the columns of the distance (or, more generally, dissimilarity) matrix d on a finite set X so that small values should be concentrated around the main diagonal as close as possible, whereas large values should fall as far from it as possible. This goal is best achieved by considering the Robinson property: a distance d (R) on X is Robinsonian if its matrix can be symmetrically permuted so that its elements do not decrease when moving away from the main diagonal along any row or column. If the distance d fails to satisfy the Robinson property, then we are lead to the problem of finding a reordering of d which is as close as possible to a Robinsonian distance. In this paper, we present a factor 16 approximation algorithm for the following NP-hard fitting problem: given a finite set X and a dissimilarity d on X, we wish to find a Robinsonian dissimilarity d (R) on X minimizing the l (a)-error aEuro-d-d (R) aEuro-(a)=max (x,yaX) {vertical bar d(x,y)-d (R) (x,y)vertical bar} between d and d (R) .
approximation algorithm fitting problem robinsonian dissimilarity