Metric violation distance: hardness and approximation

DOI10.1007/s00453-022-00940-0OpenAlexW4210896812MaRDI QIDQ2134750

Gregory van Buskirk, Chenglin Fan, Benjamin Raichel

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

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

Related Items (1)

A survey of parameterized algorithms and the complexity of edge modification

Cites Work

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

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