Skip to Main content Skip to Navigation
New interface
Conference papers

An Approximation Algorithm for l∞-Fitting Robinson Structures to Distances

Abstract : 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∞-error ||d − dR||∞ = maxx,y∈X {|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.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/inria-00359296
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Friday, February 6, 2009 - 2:59:22 PM
Last modification on : Sunday, June 26, 2022 - 12:18:00 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 10:00:38 PM

Files

chepoi_new.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00359296, version 1
  • ARXIV : 0902.1261

Collections

Citation

Victor Chepoi, Morgan Seston. An Approximation Algorithm for l∞-Fitting Robinson Structures to Distances. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.265-276. ⟨inria-00359296⟩

Share

Metrics

Record views

72

Files downloads

76