The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1 (Q5501953): Difference between revisions

Latest revision as of 15:13, 10 July 2024

scientific article; zbMATH DE number 6472767

Language	Label	Description	Also known as
English	The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ <sub>1</sub>	scientific article; zbMATH DE number 6472767

Statements

instance of

scholarly article

0 references

title

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1 (English)

0 references

0 references

0 references

0 references

14 August 2015

0 references

full work available at URL

https://arxiv.org/abs/1305.4581

0 references

zbMATH Keywords

metric embeddings

0 references

hardness of approximation

0 references

integrality gap

0 references

negative-type metrics

0 references

semidefinite programming

0 references

sparsest cut

0 references

unique games conjecture

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems

0 references

Subexponential Algorithms for Unique Games and Related Problems

0 references

Q3549678

0 references

Fréchet embeddings of negative type metrics

0 references

Expander flows, geometric embeddings and graph partitioning

0 references

An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm

0 references

The Euclidean distortion of the lamplighter group.

0 references

Making the Long Code Shorter

0 references

Q4252727

0 references

On Lipschitz embedding of finite metric spaces in Hilbert space

0 references

On the distribution of the Fourier spectrum of Boolean functions

0 references

Q2921658

0 references

On the hardness of approximating Multicut and Sparsest-Cut

0 references

Differentiating maps into $L^1$, and the geometry of BV functions

0 references

A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP

0 references

Integrality gaps for sparsest cut and minimum linear arrangement problems

0 references

Geometry of cuts and metrics

0 references

On the nonexistence of uniform homeomorphisms between $L^ p$-spaces

0 references

Improved Approximation Algorithms for Minimum Weight Vertex Separators

0 references

On the optimality of the random hyperplane rounding technique for MAX CUT

0 references

Semidefinite programming in combinatorial optimization

0 references

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

0 references

A PRG for lipschitz functions of polynomials with applications to sparsest cut

0 references

A better approximation ratio for the vertex cover problem

0 references

On the power of unique 2-prover 1-round games

0 references

Nonembeddability theorems via Fourier analysis

0 references

Q3002802

0 references

SDP Integrality Gaps with Local ell_1-Embeddability

0 references

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1

0 references

Improved Lower Bounds for Embeddings into $L_1$

0 references

Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

0 references

Q4549227

0 references

The geometry of graphs and some of its algorithmic applications

0 references

Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs

0 references

Q3549708

0 references

Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES

0 references

Graph expansion and the unique games conjecture

0 references

Block bases of the Haar system as complemented subspaces of $L{\textunderscore }p$, $2<p<\infty $

0 references

Lx = b

0 references

Identifiers

zbMATH Open document ID

1321.68316

0 references

DOI

10.1145/2629614

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5501953

@@ Property / cites work @@
+O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
+Normal rank
@@ Property / cites work @@
+Subexponential Algorithms for Unique Games and Related Problems
+Normal rank
@@ Property / cites work @@
+Q3549678
@@ Property / cites work: Q3549678 / rank @@
+Normal rank
@@ Property / cites work @@
+Fréchet embeddings of negative type metrics
@@ Property / cites work: Fréchet embeddings of negative type metrics / rank @@
+Normal rank
@@ Property / cites work @@
+Expander flows, geometric embeddings and graph partitioning
+Normal rank
@@ Property / cites work @@
+An <i>O</i>(log <i>k</i>) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
+Normal rank
@@ Property / cites work @@
+The Euclidean distortion of the lamplighter group.
+Normal rank
@@ Property / cites work @@
+Making the Long Code Shorter
@@ Property / cites work: Making the Long Code Shorter / rank @@
+Normal rank
@@ Property / cites work @@
+Q4252727
@@ Property / cites work: Q4252727 / rank @@
+Normal rank
@@ Property / cites work @@
+On Lipschitz embedding of finite metric spaces in Hilbert space
+Normal rank
@@ Property / cites work @@
+On the distribution of the Fourier spectrum of Boolean functions
+Normal rank
@@ Property / cites work @@
+Q2921658
@@ Property / cites work: Q2921658 / rank @@
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating Multicut and Sparsest-Cut
+Normal rank
@@ Property / cites work @@
+Differentiating maps into \(L^1\), and the geometry of BV functions
+Normal rank
@@ Property / cites work @@
+A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
+Normal rank
@@ Property / cites work @@
+Integrality gaps for sparsest cut and minimum linear arrangement problems
+Normal rank
@@ Property / cites work @@
+Geometry of cuts and metrics
@@ Property / cites work: Geometry of cuts and metrics / rank @@
+Normal rank
@@ Property / cites work @@
+On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
+Normal rank
@@ Property / cites work @@
+Improved Approximation Algorithms for Minimum Weight Vertex Separators
+Normal rank
@@ Property / cites work @@
+On the optimality of the random hyperplane rounding technique for MAX CUT
+Normal rank
@@ Property / cites work @@
+Semidefinite programming in combinatorial optimization
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
+Normal rank
@@ Property / cites work @@
+A PRG for lipschitz functions of polynomials with applications to sparsest cut
+Normal rank
@@ Property / cites work @@
+A better approximation ratio for the vertex cover problem
+Normal rank
@@ Property / cites work @@
+On the power of unique 2-prover 1-round games
@@ Property / cites work: On the power of unique 2-prover 1-round games / rank @@
+Normal rank
@@ Property / cites work @@
+Nonembeddability theorems via Fourier analysis
@@ Property / cites work: Nonembeddability theorems via Fourier analysis / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002802
@@ Property / cites work: Q3002802 / rank @@
+Normal rank
@@ Property / cites work @@
+SDP Integrality Gaps with Local ell_1-Embeddability
+Normal rank
@@ Property / cites work @@
+The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ             <sub>1</sub>
+Normal rank
@@ Property / cites work @@
+Improved Lower Bounds for Embeddings into $L_1$
@@ Property / cites work: Improved Lower Bounds for Embeddings into $L_1$ / rank @@
+Normal rank
@@ Property / cites work @@
+Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
+Normal rank
@@ Property / cites work @@
+Q4549227
@@ Property / cites work: Q4549227 / rank @@
+Normal rank
@@ Property / cites work @@
+The geometry of graphs and some of its algorithmic applications
+Normal rank
@@ Property / cites work @@
+Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
+Normal rank
@@ Property / cites work @@
+Q3549708
@@ Property / cites work: Q3549708 / rank @@
+Normal rank
@@ Property / cites work @@
+Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
+Normal rank
@@ Property / cites work @@
+Graph expansion and the unique games conjecture
@@ Property / cites work: Graph expansion and the unique games conjecture / rank @@
+Normal rank
@@ Property / cites work @@
+Block bases of the Haar system as complemented subspaces of $L{\textunderscore }p$, $2&lt;p&lt;\infty $
+Normal rank
@@ Property / cites work @@
+Lx = b
@@ Property / cites work: Lx = b / rank @@
+Normal rank

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ <sub>1</sub> (Q5501953): Difference between revisions

Latest revision as of 15:13, 10 July 2024

Statements

Identifiers

Sitelinks

Mathematics(1 entry)