The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ <sub>1</sub> (Q5501953)
From MaRDI portal
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
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ <sub>1</sub> (English)
0 references
14 August 2015
0 references
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
