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/2009
Entry Accepted: 10/29/2009
Entry Last Modified: 10/29/2009

Modify/Update this entry