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 is (SDP_n) 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/(\pi\gamma(m)) = 2/\pi + \Theta(1/m), and we determine the optimal constant of the positive semidefinite case of a generalized Grothendieck inequality.
Additional Metadata
Keywords Grothendieck’s inequality, semidefinite programming, approximation algorithms, unique games conjecture, functions of positive type
MSC Approximation algorithms (msc 68W25)
THEME Life Sciences (theme 5), Logistics (theme 3), Logistics (theme 3)
Publisher Springer
Editor S. Abramsky , C. Gavoille , C. Kirchner (Claude) , F. Meyer auf der Heide , P.G. Spirakis (Paul)
Conference International Colloquium on Automata, Languages and Programming
Briët, J, de Oliveira Filho, F.M, & Vallentin, F. (2010). The positive semidefinite Grothendieck problem with rank constraint. In S Abramsky, C Gavoille, C Kirchner, F Meyer auf der Heide, & P.G Spirakis (Eds.), Proceedings of Automata, Languages and Programming, International Colloquium 2010. Springer.