An Approximation Algorithm for l\infty-Fitting Robinson Structures to Distances

Simple item page
dc.creatorChepoi, Victor
dc.creatorSeston, M.
dc.date2009-02-07
dc.date.accessioned2026-07-07T12:39:21Z
dc.date.available2026-07-07T12:39:21Z
dc.descriptionIn 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 dR on X minimizing the l\infty-error ||d - dR||\infty = maxx,y\epsilonX {|d(x, y) - dR(x, y)|}. A distance dR 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 diagonal along any row or column. Robinsonian distances generalize ultrametrics, line distances and occur in the seriation problems and in classification.
dc.identifierhttps://arxiv.org/abs/0902.1261
dc.identifierhttp://arxiv.org/abs/0902.1261
dc.identifier26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 265-276
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/219077
dc.subjectData Structures and Algorithms
dc.subjectComputational Complexity
dc.titleAn Approximation Algorithm for l\infty-Fitting Robinson Structures to Distances
dc.typetext

Files

Collections

arXiv