Fitting Various Metrics with Minimum Disagreements

Let C be a class of metric spaces. We consider the following computational metric embedding problem: given a vector x in R^{n choose 2} representing pairwise distances between n points, change the minimum number of entries of x to ensure that the new distances correspond to a metric in C. Several instantiations of this problem have been actively studied in theoretical computer science and machine learning, including Correlation Clustering (when C is the class of uniform metrics) and Metric Violation Distance (when C is the class of all metrics).

We present a unified framework and improved approximation algorithms for these metric embedding problems. One common tool is the application of the "pivot algorithm," originally developed for uniform metrics, to more general metrics. We also use connections between metric embedding and constraint satisfaction problems, which allows us to use stronger convex relaxations based on the Sherali-Adams hierarchy.

Based on joint work with Vincent Cohen-Addad, Chenglin Fan, Arnaud de Mesmay, and Alantha Newman.