文章基本信息

标题：Grothendieck Inequalities for Semidefinite Programs with Rank Constraint
本地全文：下载
作者：Jop Briët ; Fernando Mário de Oliveira Filho ; Frank Vallentin 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2014
卷号：10
页码：77-105
出版社：University of Chicago
摘要：Grothendieck inequalities are fundamental inequalities which are frequently used in many areas of mathematics and computer science. They can be interpreted as upper bounds for the integrality gap between two optimization problems: a difficult semidefinite program with rank-1 constraint and its easy semidefinite relaxation where the rank constraint is dropped. For instance, the integrality gap of the Goemans-Williamson approximation algorithm for MAX CUT can be seen as a Grothendieck inequality. In this paper we consider Grothendieck inequalities for ranks greater than $1$ and we give two applications: approximating ground states in the $n$-vector model in statistical mechanics and XOR games in quantum information theory.
关键词：randomized rounding; Grothendieck inequality; $n$-vector model; XOR games