Seriation in the presence of errors: NP-hardness of l_-fitting Robinson structures to dissimilarity matrices
From MaRDI portal
Publication:263094
Recommendations
- Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
- An approximation algorithm for \(\ell_{\infty}\) fitting Robinson structures to distances
- A branch-and-bound algorithm for fitting anti-Robinson structures to symmetric dissimilarity matrices
- An optimal algorithm to recognize Robinsonian dissimilarities
- A structural characterization for certifying Robinsonian matrices
- The robust set problem: parameterized complexity and approximation
- Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
- Erratum: ``The approximability of the exemplar breakpoint distance problem
Cites work
- \(l_\infty\)-approximation via subdominants.
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- A robust model for finding optimal evolutionary tree
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- Fitting points on the real line and its application to RH mapping
- Geometry of cuts and metrics
- scientific article; zbMATH DE number 3843553 (Why is no real title available?)
- scientific article; zbMATH DE number 4213811 (Why is no real title available?)
- scientific article; zbMATH DE number 953009 (Why is no real title available?)
- scientific article; zbMATH DE number 3996907 (Why is no real title available?)
- scientific article; zbMATH DE number 1839431 (Why is no real title available?)
- scientific article; zbMATH DE number 1865935 (Why is no real title available?)
- scientific article; zbMATH DE number 802809 (Why is no real title available?)
- Incidence matrices, interval graphs and seriation in archeology
- NP-hard approximation problems in overlapping clustering.
- On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
- Optimal narrowing of a block of sortings in optimal time
- Recognition of Robinsonian dissimilarities
- Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
- SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
- Some boundary conditions for a monotone analysis of symmetric matrices
- The complexity of satisfiability problems
Cited in
(16)- NP-hard approximation problems in overlapping clustering.
- The weighted sitting closer to friends than enemies problem in the line
- Reconstruction of line-embeddings of graphons
- Robinsonian matrices: recognition challenges
- An optimal algorithm to recognize Robinsonian dissimilarities
- Measuring indifference: unit interval vertex deletion
- An Optimal Algorithm for Strict Circular Seriation
- Similarity-first search: a new algorithm with application to Robinsonian matrix recognition
- An optimization parameter for seriation of noisy data
- An approximation algorithm for \(\ell_{\infty}\) fitting Robinson structures to distances
- A Simple and Optimal Algorithm for Strict Circular Seriation
- Modules in Robinson Spaces
- Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
- Two simple but efficient algorithms to recognize Robinson dissimilarities
- Seriation of Tœplitz and latent position matrices: optimal rates and computational trade-offs
- Tree-Robinson dissimilarities
This page was built for publication: Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q263094)
