The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
type: Item
instance of: scholarly article
title: The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
zbMATH Open document ID: 1321.68316
DOI: 10.1145/2629614
author: Subhash Khot
author: Nisheeth K. Vishnoi
published in: Journal of the ACM
publication date: 2015-08-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/1305.4581
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 90C22
zbMATH DE Number: 6472767
zbMATH Keywords: metric embeddings
zbMATH Keywords: hardness of approximation
zbMATH Keywords: integrality gap
zbMATH Keywords: negative-type metrics
zbMATH Keywords: semidefinite programming
zbMATH Keywords: sparsest cut
zbMATH Keywords: unique games conjecture
MaRDI profile type: Publication
OpenAlex ID: W2619061098
arXiv ID: 1305.4581
cites work: O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
cites work: Subexponential Algorithms for Unique Games and Related Problems
cites work: Q3549678
cites work: Fréchet embeddings of negative type metrics
cites work: Expander flows, geometric embeddings and graph partitioning
cites work: An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
cites work: The Euclidean distortion of the lamplighter group.
cites work: Making the Long Code Shorter
cites work: Q4252727
cites work: On Lipschitz embedding of finite metric spaces in Hilbert space
cites work: On the distribution of the Fourier spectrum of Boolean functions
cites work: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
cites work: On the hardness of approximating Multicut and Sparsest-Cut
cites work: Differentiating maps into \(L^1\), and the geometry of BV functions
cites work: A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
cites work: Integrality gaps for sparsest cut and minimum linear arrangement problems
cites work: Geometry of cuts and metrics
cites work: On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
cites work: Improved Approximation Algorithms for Minimum Weight Vertex Separators
cites work: On the optimality of the random hyperplane rounding technique for MAX CUT
cites work: Semidefinite programming in combinatorial optimization
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: A PRG for lipschitz functions of polynomials with applications to sparsest cut
cites work: A better approximation ratio for the vertex cover problem
cites work: On the power of unique 2-prover 1-round games
cites work: Nonembeddability theorems via Fourier analysis
cites work: Q3002802
cites work: SDP Integrality Gaps with Local ell_1-Embeddability
cites work: Improved Lower Bounds for Embeddings into $L_1$
cites work: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
cites work: Q4549227
cites work: The geometry of graphs and some of its algorithmic applications
cites work: Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
cites work: Q3549708
cites work: Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
cites work: Graph expansion and the unique games conjecture
cites work: Block bases of the Haar system as complemented subspaces of $L{\textunderscore }p$, $2<p<\infty $
cites work: Lx = b
description: scientific article; zbMATH DE number 6472767