caa a22 4500 445804882 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s00453-009-9319-y doi (NATIONALLICENCE)springer-10.1007/s00453-009-9319-y Seriation in the Presence of Errors: AFactor16Approximation Algorithm for l ∞-FittingRobinson Structures to Distances [Elektronische Daten] [Victor Chepoi, Morgan Seston] 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 ∞-error ‖d−d R‖∞=max x,y∈X{|d(x,y)−d R(x,y)|} between d and d R. Springer Science+Business Media, LLC, 2009 Robinsonian dissimilarity nationallicence Approximation algorithm nationallicence Fitting problem nationallicence Chepoi Victor Laboratoire d'Informatique Fondamentale de Marseille, Faculté des Sciences de Luminy, Université d'Aix-Marseille, 13288, Marseille Cedex 9, France aut Seston Morgan Laboratoire d'Informatique Fondamentale de Marseille, Faculté des Sciences de Luminy, Université d'Aix-Marseille, 13288, Marseille Cedex 9, France aut Algorithmica Springer-Verlag 59/4(2011-04-01), 521-568 0178-4617 59:4<521 2011 59 453 https://doi.org/10.1007/s00453-009-9319-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9319-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Chepoi Victor Laboratoire d'Informatique Fondamentale de Marseille, Faculté des Sciences de Luminy, Université d'Aix-Marseille, 13288, Marseille Cedex 9, France aut NATIONALLICENCE 700 1- Seston Morgan Laboratoire d'Informatique Fondamentale de Marseille, Faculté des Sciences de Luminy, Université d'Aix-Marseille, 13288, Marseille Cedex 9, France aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/4(2011-04-01), 521-568 0178-4617 59:4<521 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer