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

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

2009-02-07

arxiv.org/abs/0902.1261v1

26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 265-276

Computer Science

Data Structures and Algorithms

Scientific paper

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 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.

Affiliated with

Also associated with

No associations

Rating

An Approximation Algorithm for l\infty-Fitting Robinson Structures to Distances does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Approximation Algorithm for l\infty-Fitting Robinson Structures to Distances, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Approximation Algorithm for l\infty-Fitting Robinson Structures to Distances will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-312201