- The positive semidefinite Grothendieck problem with rank constraint Jop Briet (j.brietcwi.nl) Fernando M. de Oliveira Filho (f.m.de.oliveira.filhocwi.nl) Frank Vallentin (f.vallentintudelft.nl) 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 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}\left(\frac{\Gamma((n+1)/2)}{\Gamma(n/2)}\right)^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. Keywords: Grothendieck's inequality, semidefinite programming, approximation algorithms, unique games conjecture, functions of positive type, n-vector model Category 1: Linear, Cone and Semidefinite Programming Category 2: Combinatorial Optimization Citation: Download: [PDF]Entry Submitted: 10/29/2009Entry Accepted: 10/29/2009Entry Last Modified: 10/29/2009Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society.