Seriation in the presence of errors: a factor 16 approximation algorithm for l_ -fitting Robinson structures to distances
From MaRDI portal
Publication:633846
DOI10.1007/S00453-009-9319-YzbMATH Open1226.68126OpenAlexW2086738178MaRDI QIDQ633846FDOQ633846
Authors: Victor Chepoi, Morgan Seston 
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
Recommendations
- An approximation algorithm for \(\ell_{\infty}\) fitting Robinson structures to distances
- Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
- An optimal algorithm to recognize Robinsonian dissimilarities
- An optimization parameter for seriation of noisy data
- A branch-and-bound algorithm for fitting anti-Robinson structures to symmetric dissimilarity matrices
Cites Work
- Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis
- Nonmetric multidimensional scaling. A numerical method
- Multidimensional scaling. I: Theory and method
- 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
- Incidence matrices and interval graphs
- Incidence matrices, interval graphs and seriation in archeology
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
- A branch-and-bound algorithm for fitting anti-Robinson structures to symmetric dissimilarity matrices
- Title not available (Why is that?)
- Title not available (Why is that?)
- SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
- Title not available (Why is that?)
- Fitting points on the real line and its application to RH mapping
- Title not available (Why is that?)
- Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
- Relationship-based clustering and visualization for high-dimensional data mining
- Matrix visualization and information mining
- The Structural Representation of Proximity Matrices with MATLAB
- The NP-completeness column: An ongoing guide
- Approximation algorithms for low-distortion embeddings into low-dimensional spaces
- A Geometric Approach to Betweenness
- Low-distortion embeddings of general metrics into the line
- Fitting Tree Metrics: Hierarchical Clustering and Phylogeny
- Title not available (Why is that?)
- Monotone mapping of similarities into a general metric space
- On the recognition of permuted bottleneck Monge matrices
- Ordinal embeddings of minimum relaxation, general properties, trees, and ultrametrics
- Title not available (Why is that?)
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Cited In (22)
- The weighted sitting closer to friends than enemies problem in the line
- Flinders Petrie, the travelling salesman problem, and the beginning of mathematical modeling in archaeology
- Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
- An optimal algorithm to recognize Robinsonian dissimilarities
- Graph sequences sampled from Robinson graphons
- A branch-and-bound algorithm for fitting anti-Robinson structures to symmetric dissimilarity matrices
- Splitting metrics by \(T_0\)-quasi-metrics
- Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
- Convex relaxations for permutation problems
- Measuring indifference: unit interval vertex deletion
- Similarity-first search: a new algorithm with application to Robinsonian matrix recognition
- An Optimal Algorithm for Strict Circular Seriation
- Reconstruction of line-embeddings of graphons
- An approximation algorithm for \(\ell_{\infty}\) fitting Robinson structures to distances
- An optimization parameter for seriation of noisy data
- A Simple and Optimal Algorithm for Strict Circular Seriation
- Cut norm discontinuity of triangular truncation of graphons
- Modules in Robinson Spaces
- Robust recovery of Robinson property in \(L^p\)-graphons: a cut-norm approach
- \texttt{PQser:} a Matlab package for spectral seriation
- Two simple but efficient algorithms to recognize Robinson dissimilarities
- Continuation methods for approximate large scale object sequencing
Uses Software
This page was built for publication: Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\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 Q633846)
