The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n

DOI10.1145/3055399.3055413zbMath1370.68235arXiv1704.01200OpenAlexW2607237413MaRDI QIDQ4978003

Assaf Naor, Robert Young

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1704.01200

zbMATH Keywords

semidefinite programmingapproximation algorithmsmetric embeddingssparsest cut problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Vertical perimeter versus horizontal perimeter ⋮ Negative-type diversities, a multi-dimensional analogue of negative-type metrics ⋮ Unnamed Item ⋮ Semmes surfaces and intrinsic Lipschitz graphs in the Heisenberg group

This page was built for publication: The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n