Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1408.2270

A sub-constant improvement in approximating the positive semidefinite Grothendieck problem

Roy Frostig, Sida I. Wang

Published Aug 10, 2014• 0 citations
arXivHTMLPDF

Abstract

Semidefinite relaxations are a powerful tool for approximately solving combinatorial optimization problems such as MAX-CUT and the Grothendieck problem. By exploiting a bounded rank property of extreme points in the semidefinite cone, we make a sub-constant improvement in the approximation ratio of one such problem. Precisely, we describe a polynomial-time algorithm for the positive semidefinite Grothendieck problem -- based on rounding from the standard relaxation -- that achieves a ratio of $2/π+ Θ(1/{\sqrt n})$, whereas the previous best is $2/π+ Θ(1/n)$. We further show a corresponding integrality gap of $2/π+\tilde{O}(1/n^{1/3})$.

DOI
10.48550/arxiv.1408.2270

Related papers

Grothendieck inequalities for semidefinite programs with rank constraint

Jop Briët, Fernando Mário de Oliveira Filho, Frank Vallentin

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 constraint is dropped. For instance, the integrality gap of the Goemans-Williamson approximation algorithm for MAX CUT can be seen as a Grothendieck inequality. In this paper we consider Grothendieck inequalities for ranks greater than $1$ and we give two applications: approximating ground states in the $n$-vector model in statistical mechanics and XOR games in quantum information theory.

arXiv:1011.1754•Theory of Computing•Jan 1, 2014•26 citations

Approximating the Little Grothendieck Problem over the Orthogonal Group

Afonso S. Bandeira, Christopher Kennedy, Amit Singer

The little Grothendieck problem (a special case of Boolean quadratic optimization) consists of maximizing P ij Cijxixj over binary variables xi 2 f 1g, where C is a positive semidenite matrix. In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given C 2 R dn dn a positive semidenite matrix, the objective is to maximize P ij tr C T ijOiO T restricting Oi to take values in the group of orthogonal matrices O(d), where Cij denotes the (ij)-th d d block of C. We propose an approximation algorithm, to which we refer as Orthogonal-Cut, to solve the little Grothendieck problem over the group of orthogonal matrices O(d) and show a constant approximation ratio. Our method is based on semidenite programming where the relaxation is inspired by the work of Goemans and Williamson in the context of the MaxCut problem. For a given d 1, we show a constant approximation ratio of 2, where d is the expected average singular value of a d d matrix with random GaussianN 0; 1 i.i.d. entries. For d = 1 we recover the known 2 = 2= approximation guarantee for the classical little Grothendieck problem. Orthogonal-Cut also serves as an approximation algorithm for several applications including the Procrustes problem where it improves over the best previously known approximation ratio of 1 2 p 2 . The little Grothendieck problem falls under the larger class of problems approximated by an algorithm recently proposed in the context of the non-commutative Grothendieck inequality. Nonetheless, our approach is simpler and gives a better approximation ratio.

•Aug 23, 2013•7 citations

Semidefinite programming approaches for stable set and max-cut problems

Lennart Sinjorgo

This thesis investigates the use of semidefinite programming (SDP) for solving (variants of) the well-known stable set and max-cut problems. Chapter 2 considers a generalization of the stable set problem, and a corresponding SDP relaxation. Similarly, Chapter 3 considers a generalization of the max-cut problem that involves complex roots of unity. Various complex SDP relaxations of this generalized max-cut problem are studied. Chapter 4 provides approximation algorithms for the quantum generalization of the max-cut problem. These approximation algorithms employ a hierarchy of SDP relaxations for noncommutative polynomial optimization problems. Chapter 5 provides an SDP algorithm for computing bounds on the stability numbers of graphs. Chapter 6 provides an SDP algorithm for solving the MAX-SAT problem. Chapters 5 and 6 provide extensive numerical results on these algorithms.

•Jan 20, 2026•0 citations

Maximizing Quadratic Programs: Extending Grothendieck's Inequality

Moses Charikar, Anthony Ian Wirth

This paper considers the following type of quadratic programming problem. Given an arbitrary matrix A, whose diagonal elements are zero, find x /spl isin/ {-1, 1}/sup n/ such that x/sup T/Ax is maximized. Our approximation algorithm for this problem uses the canonical semidefinite relaxation and returns a solution whose ratio to the optimum is in /spl Omega/(1/ logn). This quadratic programming problem can be seen as an extension to that of maximizing x/sup T/Ay (where y's components are also /spl plusmn/1). Grothendieck's inequality states that the ratio of the optimum value of the latter problem to the optimum of its canonical semidefinite relaxation is bounded below by a constant. The study of this type of quadratic program arose from a desire to approximate the maximum correlation in correlation clustering. Nothing substantive was known about this problem; we present an /spl Omega/ (1/logn) approximation, based on our quadratic programming algorithm. We can also guarantee that our quadratic programming algorithm returns a solution to the MAXCUT problem that has a significant advantage over a random assignment.

Annual Symposium on Foundations of Computer Science•Dec 23, 2004•218 citations

A note on approximating quadratic programming with rank constraint

Shenglong Hu, Zheng‐Hai Huang

The quadratic maximization problem with rank constraint means where n and m are two given positive integers with n ≤ m, Q is a given real symmetric matrix, is the unit sphere in and stands for the Euclidean inner product. In this note, motivated by Briët, Filho and Vallentin's and Ye's excellent works [J. Briët, F. Filho, and F. Vallentin, The positive semidefinite Grothendieck problem with rank constraint, Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 6198, 2010, pp. 31–42.; Y. Ye, Approximating quadratic programming with bound and quadratic constraints, Math. Program. 84 (1999), pp. 219–226], we first derive the relative approximation ratio for the above problem with arbitrary symmetric matrix Q. While Q was supposed to be positive semidefinite in [J. Briët, F. Filhom, and F. Vallentin, The positive semidefinite Grothendieck problem with rank constraint, Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 6198, 2010, pp. 31–42.]. Secondly, we extend such a relative approximation ratio to a generalization of the above optimization problem. Finally, a slightly improved relative approximation ratio for the optimization problem considered in [Y. Ye, Approximating quadratic programming with bound and quadratic constraints, Math. Program. 84 (1999), pp. 219–226] is presented.

Optimization•Nov 12, 2010•0 citations

An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem

Hallgren, Sean, Lee, Eunou, Ojas Parekh

We present a classical approximation algorithm for the MAX-2-Local Hamiltonian problem. This is a maximization version of the QMA-complete 2-Local Hamiltonian problem in quantum computing, with the additional assumption that each local term is positive semidefinite. The MAX-2-Local Hamiltonian problem generalizes NP-hard constraint satisfaction problems, and our results may be viewed as generalizations of approximation approaches for the MAX-2-CSP problem. We work in the product state space and extend the framework of Goemans and Williamson for approximating MAX-2-CSPs. The key difference is that in the product state setting, a solution consists of a set of normalized 3-dimensional vectors rather than boolean numbers, and we leverage approximation results for rank-constrained Grothendieck inequalities. For MAX-2-Local Hamiltonian we achieve an approximation ratio of 0.328. This is the first example of an approximation algorithm beating the random quantum assignment ratio of 0.25 by a constant factor.

Leibniz international proceedings in informatics•Jan 1, 2020•3 citations
Semidefinite relaxations are a powerful tool for approximately solving combinatorial optimization problems such as MAX-CUT and the Grothendieck problem. By exploiting a bounded rank property of extreme points in the semidefinite cone, we make a sub-constant improvement in the approximation ratio of one such problem. Precisely, we describe a polynomial-time algorithm for the positive semidefinite Grothendieck problem -- based on rounding from the standard relaxation -- that achieves a ratio of 2/π+Θ(1/n)2/π+ Θ(1/{\sqrt n})2/π+Θ(1/n​), whereas the previous best is 2/π+Θ(1/n)2/π+ Θ(1/n)2/π+Θ(1/n). We further show a corresponding integrality gap of 2/π+O~(1/n1/3)2/π+\tilde{O}(1/n^{1/3})2/π+O~(1/n1/3).
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 constraint is dropped. For instance, the integrality gap of the Goemans-Williamson approximation algorithm for MAX CUT can be seen as a Grothendieck inequality. In this paper we consider Grothendieck inequalities for ranks greater than 111 and we give two applications: approximating ground states in the nnn-vector model in statistical mechanics and XOR games in quantum information theory.
The little Grothendieck problem (a special case of Boolean quadratic optimization) consists of maximizing P ij Cijxixj over binary variables xi 2 f 1g, where C is a positive semidenite matrix. In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given C 2 R dn dn a positive semidenite matrix, the objective is to maximize P ij tr C T ijOiO T restricting Oi to take values in the group of orthogonal matrices O(d), where Cij denotes the (ij)-th d d block of C. We propose an approximation algorithm, to which we refer as Orthogonal-Cut, to solve the little Grothendieck problem over the group of orthogonal matrices O(d) and show a constant approximation ratio. Our method is based on semidenite programming where the relaxation is inspired by the work of Goemans and Williamson in the context of the MaxCut problem. For a given d 1, we show a constant approximation ratio of 2, where d is the expected average singular value of a d d matrix with random GaussianN 0; 1 i.i.d. entries. For d = 1 we recover the known 2 = 2= approximation guarantee for the classical little Grothendieck problem. Orthogonal-Cut also serves as an approximation algorithm for several applications including the Procrustes problem where it improves over the best previously known approximation ratio of 1 2 p 2 . The little Grothendieck problem falls under the larger class of problems approximated by an algorithm recently proposed in the context of the non-commutative Grothendieck inequality. Nonetheless, our approach is simpler and gives a better approximation ratio.
This thesis investigates the use of semidefinite programming (SDP) for solving (variants of) the well-known stable set and max-cut problems. Chapter 2 considers a generalization of the stable set problem, and a corresponding SDP relaxation. Similarly, Chapter 3 considers a generalization of the max-cut problem that involves complex roots of unity. Various complex SDP relaxations of this generalized max-cut problem are studied. Chapter 4 provides approximation algorithms for the quantum generalization of the max-cut problem. These approximation algorithms employ a hierarchy of SDP relaxations for noncommutative polynomial optimization problems. Chapter 5 provides an SDP algorithm for computing bounds on the stability numbers of graphs. Chapter 6 provides an SDP algorithm for solving the MAX-SAT problem. Chapters 5 and 6 provide extensive numerical results on these algorithms.
This paper considers the following type of quadratic programming problem. Given an arbitrary matrix A, whose diagonal elements are zero, find x /spl isin/ {-1, 1}/sup n/ such that x/sup T/Ax is maximized. Our approximation algorithm for this problem uses the canonical semidefinite relaxation and returns a solution whose ratio to the optimum is in /spl Omega/(1/ logn). This quadratic programming problem can be seen as an extension to that of maximizing x/sup T/Ay (where y's components are also /spl plusmn/1). Grothendieck's inequality states that the ratio of the optimum value of the latter problem to the optimum of its canonical semidefinite relaxation is bounded below by a constant. The study of this type of quadratic program arose from a desire to approximate the maximum correlation in correlation clustering. Nothing substantive was known about this problem; we present an /spl Omega/ (1/logn) approximation, based on our quadratic programming algorithm. We can also guarantee that our quadratic programming algorithm returns a solution to the MAXCUT problem that has a significant advantage over a random assignment.
The quadratic maximization problem with rank constraint means where n and m are two given positive integers with n ≤ m, Q is a given real symmetric matrix, is the unit sphere in and stands for the Euclidean inner product. In this note, motivated by Briët, Filho and Vallentin's and Ye's excellent works [J. Briët, F. Filho, and F. Vallentin, The positive semidefinite Grothendieck problem with rank constraint, Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 6198, 2010, pp. 31–42.; Y. Ye, Approximating quadratic programming with bound and quadratic constraints, Math. Program. 84 (1999), pp. 219–226], we first derive the relative approximation ratio for the above problem with arbitrary symmetric matrix Q. While Q was supposed to be positive semidefinite in [J. Briët, F. Filhom, and F. Vallentin, The positive semidefinite Grothendieck problem with rank constraint, Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 6198, 2010, pp. 31–42.]. Secondly, we extend such a relative approximation ratio to a generalization of the above optimization problem. Finally, a slightly improved relative approximation ratio for the optimization problem considered in [Y. Ye, Approximating quadratic programming with bound and quadratic constraints, Math. Program. 84 (1999), pp. 219–226] is presented.
We present a classical approximation algorithm for the MAX-2-Local Hamiltonian problem. This is a maximization version of the QMA-complete 2-Local Hamiltonian problem in quantum computing, with the additional assumption that each local term is positive semidefinite. The MAX-2-Local Hamiltonian problem generalizes NP-hard constraint satisfaction problems, and our results may be viewed as generalizations of approximation approaches for the MAX-2-CSP problem. We work in the product state space and extend the framework of Goemans and Williamson for approximating MAX-2-CSPs. The key difference is that in the product state setting, a solution consists of a set of normalized 3-dimensional vectors rather than boolean numbers, and we leverage approximation results for rank-constrained Grothendieck inequalities. For MAX-2-Local Hamiltonian we achieve an approximation ratio of 0.328. This is the first example of an approximation algorithm beating the random quantum assignment ratio of 0.25 by a constant factor.