An approximation algorithm for _ fitting Robinson structures to distances

DOI10.4230/LIPICS.STACS.2009.1816MaRDI QIDQ5389983zbMATH OpenOpenAlexFDO

Authors Victor Chepoi, Morgan Seston

Publication date 24 April 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_f474.html

zbMATH Keywords

approximation algorithmfitting problemRobinsonian dissimilarity

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Approximation algorithms (68W25)

Recommendations

• Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
• Fitting distances by tree metrics with increment error
• Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
• On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
• Robinsonian matrices: recognition challenges

Cited in

(2)

• Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
• Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances

Describes a project that uses

Uses Software

• PermutMatrix
• seriation

This page was built for publication: An approximation algorithm for \(\ell_{\infty}\) fitting Robinson structures to distances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5389983)