Optimization Online


The positive semidefinite Grothendieck problem with rank constraint

Jop Briet (j.briet***at***cwi.nl)
Fernando M. de Oliveira Filho (f.m.de.oliveira.filho***at***cwi.nl)
Frank Vallentin (f.vallentin***at***tudelft.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


Download: [PDF]

Entry Submitted: 10/29/2009
Entry Accepted: 10/29/2009
Entry Last Modified: 10/29/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society