Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut

DOI10.1145/1361192.1361199zbMath1445.68246OpenAlexW3137884736MaRDI QIDQ4962715

Anupam Gupta, Harald Räcke, Shuchi Chawla

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://figshare.com/articles/journal_contribution/Embeddings_of_Negative-type_Metrics_and_An_Improved_Approximation_to_Generalized_Sparsest_Cut/6605168

zbMATH Keywords

embeddingapproximation algorithmmetricssparsest cutnegative-type metric

Mathematics Subject Classification ID

Metric spaces, metrizability (54E35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items

On a class of metrics related to graph layout problems ⋮ On the Structure of Isometrically Embeddable Metric Spaces ⋮ Approximating Requirement Cut via a Configuration LP