Preprint
Oct 2026
How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics
Given a complete graph whose edge weights represent dissimilarities, Metric Violation Distance asks whether at most $k$ weights can be changed to form a metric. Motivated by metric repair for noisy data, the problem admits a polynomial-time $O(\log n)$-approximation due to Cohen-Addad, Fan, Lee and de Mesmay [SIAM J. C...
Sayan Bandyapadhyay, William Lochet, D. Lokshtanov et al.
· 0 citations