Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
From MaRDI portal
Publication:633846
DOI10.1007/s00453-009-9319-yzbMath1226.68126OpenAlexW2086738178MaRDI QIDQ633846
Publication date: 30 March 2011
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-009-9319-y
Related Items
An optimal algorithm to recognize Robinsonian dissimilarities ⋮ A Simple and Optimal Algorithm for Strict Circular Seriation ⋮ Reconstruction of line-embeddings of graphons ⋮ Cut norm discontinuity of triangular truncation of graphons ⋮ Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition ⋮ Graph sequences sampled from Robinson graphons ⋮ Modules in Robinson Spaces ⋮ Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances ⋮ An Optimization Parameter for Seriation of Noisy Data ⋮ Splitting metrics by \(T_0\)-quasi-metrics ⋮ Measuring Indifference: Unit Interval Vertex Deletion ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ The weighted sitting closer to friends than enemies problem in the line ⋮ An Optimal Algorithm for Strict Circular Seriation ⋮ Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
Uses Software
Cites Work
- A branch-and-bound algorithm for fitting anti-Robinson structures to symmetric dissimilarity matrices
- Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
- Monotone mapping of similarities into a general metric space
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- 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
- On the recognition of permuted bottleneck Monge matrices
- Incidence matrices and interval graphs
- Incidence matrices, interval graphs and seriation in archeology
- Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis
- Nonmetric multidimensional scaling. A numerical method
- Multidimensional scaling. I: Theory and method
- Relationship-Based Clustering and Visualization for High-Dimensional Data Mining
- Fitting Tree Metrics: Hierarchical Clustering and Phylogeny
- Low-distortion embeddings of general metrics into the line
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- A Geometric Approach to Betweenness
- 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
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- The Structural Representation of Proximity Matrices with MATLAB
- The NP-completeness column: An ongoing guide
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
