Metric violation distance: hardness and approximation

DOI10.1007/S00453-022-00940-0MaRDI QIDQ2134750zbMATH OpenOpenAlexFDO

Authors Chenglin Fan, Benjamin Raichel, Gregory van Buskirk

Publication date 3 May 2022

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-022-00940-0

zbMATH Keywords

approximationhardnessmetrics

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Recommendations

• Metric violation distance: hardness and approximation
• Fitting metrics and ultrametrics with minimum disagreements
• The Metric Nearness Problem
• Finding the closest ultrametric
• On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)

Cites work

• Distance realization problems with applications to internet tomography
• Generalized Metric Repair on Graphs
• Metric embeddings with outliers
• Metric embeddings with relaxed guarantees
• Metric violation distance: hardness and approximation
• On Lipschitz embedding of finite metric spaces in Hilbert space
• P-Complete Approximation Problems
• The geometry of graphs and some of its algorithmic applications
• The Metric Nearness Problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Worst-case analysis of a new heuristic for the travelling salesman problem

Cited in

(3)

• A survey of parameterized algorithms and the complexity of edge modification
• Fitting metrics and ultrametrics with minimum disagreements
• An efficient CGA\_ADMM for the metric nearness problem

This page was built for publication: Metric violation distance: hardness and approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2134750)