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.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.265-276, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00359296
Contributeur : Publications Loria <>
Soumis le : vendredi 6 février 2009 - 14:59:22
Dernière modification le : vendredi 9 mars 2018 - 11:24:56
Document(s) archivé(s) le : mardi 8 juin 2010 - 22:00:38

Fichiers

chepoi_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.265-276, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359296〉

Partager

Métriques

Consultations de la notice

110

Téléchargements de fichiers

104