The positive semidefinite Grothendieck problem with rank constraint

DOI10.1007/978-3-642-14165-2_4zbMATH Open1287.68178arXiv0910.5765OpenAlexW1547393877MaRDI QIDQ3587367FDOQ3587367

Fernando Mário de Oliveira Filho, Frank Vallentin, Jop Briët

Publication date: 7 September 2010

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Abstract: Given a positive integer n and a positive semidefinite matrix A = (A_{ij}) of size m x m, the positive semidefinite Grothendieck problem with rank-n-constraint (SDP_n) is maximize sum_{i=1}^m sum_{j=1}^m A_{ij} x_i cdot x_j, where x_1, ..., x_m in S^{n-1}. In this paper we design a polynomial time approximation algorithm for SDP_n achieving an approximation ratio of gamma(n) = frac{2}{n}(frac{Gamma((n+1)/2)}{Gamma(n/2)})^2 = 1 - Theta(1/n). We show that under the assumption of the unique games conjecture the achieved approximation ratio is optimal: There is no polynomial time algorithm which approximates SDP_n with a ratio greater than gamma(n). We improve the approximation ratio of the best known polynomial time algorithm for SDP_1 from 2/pi to 2/(pigamma(m)) = 2/pi + Theta(1/m), and we show a tighter approximation ratio for SDP_n when A is the Laplacian matrix of a graph with nonnegative edge weights.

Full work available at URL: https://arxiv.org/abs/0910.5765

Mathematics Subject Classification ID

Quadratic programming (90C20) Randomized algorithms (68W20) Approximation algorithms (68W25)

Cited In (12)

• On the largest Bell violation attainable by a quantum state
• Grothendieck’s Theorem, past and present
• Title not available (Why is that?)
• Grothendieck-type inequalities in combinatorial optimization
• Title not available (Why is that?)
• Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators
• Rational and real positive semidefinite rank can be different
• Approximating the little Grothendieck problem over the orthogonal and unitary groups
• Grothendieck constant is norm of Strassen matrix multiplication tensor
• Grothendieck inequalities for semidefinite programs with rank constraint
• A generalized Grothendieck inequality and nonlocal correlations that require high entanglement
• Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs

   Recommendations

• Approximating the little Grothendieck problem over the orthogonal and unitary groups 👍 👎
• SDP gaps and UGC-hardness for max-cut-gain 👍 👎
• Title not available (Why is that?) 👍 👎
• Grothendieck inequalities for semidefinite programs with rank constraint 👍 👎
• THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND 👍 👎

This page was built for publication: The positive semidefinite Grothendieck problem with rank constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587367)