  


The positive semidefinite Grothendieck problem with rank constraint
Jop Briet (j.brietcwi.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 ranknconstraint 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^{n1}. 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, nvector model Category 1: Linear, Cone and Semidefinite Programming Category 2: Combinatorial Optimization Citation: Download: [PDF] Entry Submitted: 10/29/2009 Modify/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  