2026-07-23T02:51:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1816 2024-03-06T10:33:10Z ddc:004 open_access

An Approximation Algorithm for l_infinity Fitting Robinson Structures to Distances Chepoi, Victor Seston, Morgan Robinsonian dissimilarity Approximation algorithm Fitting problem In this paper, we present a factor 16 approximation algorithm for the following NP-hard distance fitting problem: given a finite set $X$ and a distance $d$ on $X$, find a Robinsonian distance $d_R$ on $X$ minimizing the $l_{\infty}$-error $||d-d_R||_{\infty}=\mbox{max}_{x,y\in X}\{ |d(x,y)-d_R(x,y)|\}.$ A distance $d_R$ on a finite set $X$ is Robinsonian if its matrix can be symmetrically permuted so that its elements do not decrease when moving away from the main diagonalalong any row or column. Robinsonian distances generalize ultrametrics, line distances and occur in the seriation problems and in classification. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Victor Chepoi and Morgan Seston 2009 Is Part Of LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2009.1816 urn:nbn:de:0030-drops-18167 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1816 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode