n-vector model

Grothendieck inequalities for semidefinite programs with rank constraint

  • Jop Briet
  • Fernando Mário de Oliveira Filho
  • Frank Vallentin
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    Grothendieck inequalities are fundamental inequalities which are frequently used in many areas of mathematics and computer science. They can be interpreted as upper bounds for the integrality gap between two optimization problems: A difficult semidefinite program with rank-1 constraint and its easy semidefinite relaxation where the rank constrained is dropped. For instance, the integrality gap … Read more

    The positive semidefinite Grothendieck problem with rank constraint

  • Jop Briet
  • Fernando Mário de Oliveira Filho
  • Frank Vallentin
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    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 … Read more