On the integrality gap of the maximum-cut semidefinite programming relaxation in fixed dimension

On the integrality gap of the maximum-cut semidefinite programming relaxation in fixed dimension, Discrete Analysis 2020:10, 17 pp.

MAXCUT, the problem of finding a partition of the vertices of a given graph into two sets that maximizes the number of edges between the sets, is an important optimization problem with many algorithmic applications. Unfortunately, it is NP-complete, but many interesting results have been proved about approximating the best answer. In particular, Goemans and Williamson proved a fundamental result that showed that a semidefinite programming relaxation of the problem gives an answer that is not too far from the best possible.

To see how this works, one first observes that the problem of finding a cut of maximum size in a graph $G$ is equivalent to maximizing the sum

$$\sum_{xy\in E(G)}(1-f(x)f(y))$$

over all functions $f:V(G)\to\{-1,1\}$. Indeed, if $A$ and $B$ are the sets where $f(x)=1$ and $-1$, respectively, then $1-f(x)f(y)=0$ if $x$ and $y$ are in the same set and $2$ if they are in different sets, so the maximum of this sum is equal to twice the size of the maximum cut.

The SDP relaxation of this problem (here, SDP stands for semidefinite programming) is where we replace the above maximum by the maximum of

$$\sum_{xy\in E(G)}(1-\langle f(x),f(y)\rangle)$$

where $f$ takes values in the unit sphere of an arbitrary Euclidean space. Note that the original problem is just the case where the Euclidean space is 1-dimensional.

The reason for the word “semidefinite” here is that an $n\times n$ matrix $M$ is positive semidefinite if and only if there are $n$ vectors $x_1,\dots,x_n$ in a Euclidean space such that $M_{ij}=\langle x_i,x_j\rangle$ for every $i,j$. (Of course, in this case we place the additional constraint that $x_i$ are unit vectors, which is equivalent to the additional condition that every diagonal entry of $M$ is equal to 1.)

The famous result of Goemans and Williamson is that the maximum for the SDP relaxation is always within a constant (independent of the size of the graph) of the maximum for the original MAXCUT problem. Moreover, the constant is fairly close to 1. This is useful, because there are efficient algorithms for solving SDP problems, and therefore there are efficient algorithms for approximating reasonably well the size of the max cut.

In fact, their result is more general, since it applies to all non-negative matrices, and not just to adjacency matrices of graphs. That is, it concerns more general sums of the form

$$\sum_{x,y}A(x,y)(1-\langle f(x),f(y)\rangle).$$

It is reminiscent of Grothendieck’s theorem, in that it shows that one can replace $\pm 1$ values by more general unit vectors at the loss of a constant factor, but the conditions are slightly different.

This paper is concerned with what happens if the values of $f$ are required to be unit vectors in an $n$-dimensional space. Let us define SDP$_n(A)$ to be the maximum over such functions $f$, and let us define $\alpha_n$ to be the infimum of SDP$_1(A)/$SDP$_n(A)$ over all non-negative matrices $A$. The result of Goemans and Williamson is that $\alpha_\infty>0$ (in fact, it is approximately 0.87856), but we can also ask what $\alpha_n$ is for finite values of $n$. Note that SDP$_n(A)$ increases with $n$, so $\alpha_n$ decreases. The phrase “integrality gap” in the title of the paper refers to the gap between $\alpha_n$ and $\alpha_1=1$, since it measures how large the gap is between the best answers for relaxations of problems of this type, and the best answers for the original problems where $f$ is required to take integer values.

Previous results have tackled only the cases $n=2$ and $n=3$, but the main result of the paper is to formulate for each $n$ what the authors call a factor-revealing optimization problem. By this they mean an optimization problem that has $\alpha_n$ as its optimal value. The factor-revealing problem is NP-complete, but it is neat and fairly simple to state (see Theorem 1.1 of the paper), and once they have formulated it and proved that the optimal value is indeed $\alpha_n$, they can use relaxations to obtain upper bounds for the $\alpha_n$. Some of the values they obtain are tabulated on page 14 of the paper. The proof that the problem is factor revealing makes interesting and non-trivial use of orthogonal polynomials.