Fitting metrics and ultrametrics with minimum disagreements
DOI10.1137/22M1520190MaRDI QIDQ6670352FDOQ6670352
Authors: Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay 
Publication date: 23 January 2025
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Metric embeddings as related to computational problems and algorithms (68R12)
Cites Work
- Clustering with qualitative information
- Aggregating inconsistent information: ranking and clustering
- On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
- Analysis of Boolean Functions
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Gaussian bounds for noise correlation of functions
- On the hardness of approximating Multicut and Sparsest-Cut
- Title not available (Why is that?)
- On the power of unique 2-prover 1-round games
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Characterization, stability and convergence of hierarchical clustering methods
- On weighted vs unweighted versions of combinatorial optimization problems
- Length-bounded cuts and flows
- New results on optimizing rooted triplets consistency
- Approximating maximum subgraphs without short cycles
- Packing directed circuits fractionally
- Title not available (Why is that?)
- Fitting Tree Metrics: Hierarchical Clustering and Phylogeny
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Subcubic equivalences between path, matrix, and triangle problems
- Hardness of Graph Pricing Through Generalized Max-Dicut
- Approximate hierarchical clustering via sparsest cut and spreading metrics
- The Metric Nearness Problem
- Hierarchical clustering. Objective functions and algorithms
- Hierarchical clustering better than average-linkage
- Metric embeddings with outliers
- Metric violation distance: hardness and approximation
- Improved hardness for cut, interdiction, and firefighter problems
- Circumventing \(d\)-to-\(1\) for approximation resistance of satisfiable predicates strictly containing parity of width at least four
This page was built for publication: Fitting metrics and ultrametrics with minimum disagreements
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6670352)
