Sharp kernel clustering algorithms and their associated Grothendieck inequalities

DOI10.1002/rsa.20398zbMath1294.90045OpenAlexW2086419019MaRDI QIDQ4921885

Subhash A. Khot, Assaf Naor

Publication date: 28 May 2013

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20398

zbMATH Keywords

semidefinite programmingapproximation algorithmsunique games hardness

Mathematics Subject Classification ID

Semidefinite programming (90C22) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (3)

Solution of the propeller conjecture in \(\mathbb R^3\) ⋮ Low correlation noise stability of symmetric sets ⋮ Grothendieck constant is norm of Strassen matrix multiplication tensor

Cites Work

• Limit theorems for polylinear forms
• A proof of the Grothendieck inequality
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Near-optimal algorithms for unique games

This page was built for publication: Sharp kernel clustering algorithms and their associated Grothendieck inequalities