The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n
type: Item
instance of: scholarly article
title: The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n
zbMATH Open document ID: 1370.68235
DOI: 10.1145/3055399.3055413
author: Assaf Naor
author: Robert Young
publication date: 2017-08-17T00:00:00Z
full work available at URL: https://arxiv.org/abs/1704.01200
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 6761838
zbMATH Keywords: sparsest cut problem
zbMATH Keywords: approximation algorithms
zbMATH Keywords: metric embeddings
zbMATH Keywords: semidefinite programming
MaRDI profile type: Publication
OpenAlex ID: W2607237413
arXiv ID: 1704.01200
published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
description: scientific article; zbMATH DE number 6761838