Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices

DOI10.1007/s00357-009-9041-0zbMath1337.68114OpenAlexW1996697881MaRDI QIDQ263094

Bernard Fichet, Morgan Seston, Victor Chepoi

Publication date: 4 April 2016

Published in: Journal of Classification (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00357-009-9041-0

zbMATH Keywords

NP-hardness\(l_{\infty}\)-normfitting problemRobinsonian dissimilarity

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (10)

An optimal algorithm to recognize Robinsonian dissimilarities ⋮ A Simple and Optimal Algorithm for Strict Circular Seriation ⋮ Reconstruction of line-embeddings of graphons ⋮ Robinsonian matrices: recognition challenges ⋮ Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition ⋮ Modules in Robinson Spaces ⋮ An Optimization Parameter for Seriation of Noisy Data ⋮ Measuring Indifference: Unit Interval Vertex Deletion ⋮ The weighted sitting closer to friends than enemies problem in the line ⋮ An Optimal Algorithm for Strict Circular Seriation

Uses Software

• PermutMatrix

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Recognition of Robinsonian dissimilarities
• NP-hard approximation problems in overlapping clustering.
• \(l_\infty\)-approximation via subdominants.
• A robust model for finding optimal evolutionary tree
• Optimal narrowing of a block of sortings in optimal time
• Incidence matrices, interval graphs and seriation in archeology
• Some boundary conditions for a monotone analysis of symmetric matrices
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
• SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
• Fitting points on the real line and its application to RH mapping
• The complexity of satisfiability problems
• Geometry of cuts and metrics

This page was built for publication: Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices