文章基本信息

标题：An Approximation Algorithm for l_infinity Fitting Robinson Structures to Distances
本地全文：下载
作者：Victor Chepoi ; Morgan Seston
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2009
卷号：3
页码：265-276
DOI：10.4230/LIPIcs.STACS.2009.1816
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Robinsonian dissimilarity; Approximation algorithm; Fitting problem