Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams

Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins +2

Metric embeddings are a widely used method in algorithm design, where generally a ``complex'' metric is embedded into a simpler, lower-dimensional one. Historically, the theoretica…