Semidefinite Programming

and Combinatorial Optimization

Michel X. Goemans^{1}

Abstract. We describe a few applications of semidefinite programming in combinatorial optimization.

1991 Mathematics Subject Classification: 90C25, 90C10, 90C27, 05C50, 05C60, 68R10. Keywords and Phrases: Convex optimization, combinatorial optimization, semidefinite programming, eigenvalue bounds.

Semidefinite programming is a special case of convex programming where the feasible region is an affine subspace of the cone of positive semidefinite matrices. There has been much interest in this area lately, partly because of applications in combinatorial optimization and in control theory and also because of the development of efficient interior-point algorithms.

The use of semidefinite programming in combinatorial optimization is not new though. Eigenvalue bounds have been proposed for combinatorial optimization problems since the late 60’s, see for example the comprehensive survey by Mohar and Poljak [20]. These eigenvalue bounds can often be recast as semidefinite programs [1]. This reformulation is useful since it allows to exploit properties of convex programming such as duality and polynomial-time solvability, and it avoids the pitfalls of eigenvalue optimization such as non-differentiability. An explicit use of semidefinite programming in combinatorial optimization appeared in the seminal work of Lovász [16] on the so-called theta function, and this lead Grötschel, Lovász and Schrijver [9, 11] to develop the only known (and non-combinatorial) polynomial-time algorithm to solve the maximum stable set problem for perfect graphs.

In this paper, we describe a few applications of semidefinite programming in combinatorial optimization. Because of space limitations, we restrict our attention to the Lovász theta function, the maximum cut problem [8], and the automatic generation of valid inequalities à la Lovász-Schrijver [17, 18]. This survey is much inspired by another (longer) survey written by the author [7]. However, new results on the power and limitations of the Lovász-Schrijver procedure are presented as well as a study of the maximum cut relaxation for graphs arising from association schemes.

1Supported in part by NSF contract 9623859-CCR.

Documenta Mathematica · Extra Volume ICM 1998 · III · 657–666

1 Preliminaries

In this section, we collect several basic results about positive semidefinite matrices and semidefinite programming.

Let M_{n} denote the cone of n × n matrices (over the reals), and let S_{n} denote the subcone of symmetric n × n matrices. A matrix A ∈ S_{n} is said to be positive semidefinite if its associated quadratic form x^{T} Ax is nonnegative for all x ∈ R^{n}. The positive semidefiniteness of a matrix A will be denoted by A ⪰ 0; similarly, we write A ⪰ B for A − B ⪰ 0. The cone of positive semidefinite matrices will be denoted by P SD_{n}. The following statements are equivalent for a symmetric matrix A: (i) A is positive semidefinite, (ii) all eigenvalues of A are nonnegative, and (iii) there exists a matrix B such that A = B^{T} B. (iii) gives a representation of A = [a_{ij}] as a Gram matrix: there exist vectors v_{i} such that a_{ij} = v_{i}^{T} v_{j} for all i, j. Given a symmetric positive semidefinite matrix A, a matrix B satisfying (iii) can be obtained in O(n^{3}) time by a Cholesky decomposition.

Given A, B ∈ M_{n}, the (Frobenius) inner product A • B is defined by A • B = T r(A^{T} B) = ∑_{i} ∑_{j} A_{ij}B_{ij}. The quadratic form x^{T} Ax can thus also be written as A • (xx^{T}). Since the extreme rays of P SD_{n} are of the form xx^{T}, we derive that A • B ≥ 0 whenever A, B ⪰ 0. We can also similarly derive Fejer’s theorem which says that P SD_{n} is self-polar, i.e. P SD_{n}^{∗} = {A ∈ S_{n} : A • B ≥ 0 for all B ⪰ 0} = P SD_{n}.

Semidefinite programs are linear programs over the cone of positive semidefinite matrices. They can be expressed in many equivalent forms, e.g.

SDP = inf C • Y  (1)
subject to: A_{i} • Y = b_{i} i = 1, ⋯, m
Y ⪰ 0.

In general a linear program over a pointed closed convex cone K is formulated as z = inf{c^{T} x : Ax = b, x ∈ K}, and its dual (see [22]) is w = sup{b^{T} y : A^{T} y + s = c, s ∈ K^{∗}} where K^{∗} = {a : a^{T} b ≥ 0 for all b ∈ K}. Weak duality always holds: c^{T} x − y^{T} b = (A^{T} y + s)^{T} x − y^{T} Ax = s^{T} x for any primal feasible x and dual feasible y. If we assume that A has full row rank, {x ∈ intK} ≠ ∅, and {(y, s) : A^{T} y + s = c, s ∈ int K^{∗}} ≠ ∅, then z = w and both the primal and dual problems attain their optimum value. In the case of semidefinite programs, the dual to (1) is sup{∑_{i=1}^{n} b_{i}y_{i} : ∑_{i} y_{i}A_{i} ⪯ C}.

Semidefinite programs can be solved (more precisely, approximated) in polynomial-time within any specified accuracy either by the ellipsoid algorithm [9, 11] or more efficiently through interior-point algorithms. For the latter, we refer the reader to [22, 1, 24]. The above algorithms produce a strictly feasible solution (or slightly infeasible for some versions of the ellipsoid algorithm) and, in fact, the problem of deciding whether a semidefinite program is feasible (exactly)

is still open. However, we should point out that since ( \begin{matrix}1 & x \\ x & a \end{matrix} ) ⪰ 0 iff |x| ≤ \sqrt{a},

a special case of semidefinite programming feasibility is the square-root sum problem: given a_{1}, ⋯, a_{n} and k, decide whether ∑_{i=1}^{n} \sqrt{a_{i}} ≤ k. The complexity of this problem is still open.

2 Lovász’s Theta Function

Given a graph G = (V, E), a stable (or independent) set is a subset S of vertices such that no two vertices of S are adjacent. The maximum cardinality of a stable set is the stability number (or independence number) of G and is denoted by α(G). In a seminal paper [16], Lovász proposed an upper bound on α(G) known as the theta function ϑ(G). The theta function can be expressed in many equivalent ways, as an eigenvalue bound, as a semidefinite program, or in terms of orthogonal representations. These formulations will be summarized in this section. We refer the reader to the original paper [16], to Chapter 9 in Grötschel et al. [11], or to the survey by Knuth [15] for additional details.

As an eigenvalue bound, ϑ(G) can be derived as follows. Consider P = {A ∈ S_{n} : a_{ij} = 1 if (i, j) ∉ E (or i = j)}. If there exists a stable set of size k, the corresponding principal submatrix of any A ∈ P will be J_{k}, the all ones matrix of size k. By a classical result on interlacing of eigenvalues for symmetric matrices (see [13]), we derive that λ_{max}(A) ≥ λ_{max}(J_{k}) = k for any A ∈ P, where λ_{max}(·) denotes the largest eigenvalue. As a result, min_{A∈P} λ_{max}(A) is an upper bound on α(G), and this is one of the equivalent formulations of Lovász’s theta function.

This naturally leads to a semidefinite program. Indeed, the largest eigenvalue of a matrix can easily be formulated as a semidefinite program: λ_{max}(A) = min{t : tI − A ⪰ 0}. In order to express ϑ(G) as a semidefinite program, we observe that A ∈ P is equivalent to A − J being generated by E_{ij} for (i, j) ∈ E, where all entries of E_{ij} are zero except for (i, j) and (j, i). Thus, we can write

ϑ(G) = min t
subject to:  tI + ∑_{(i,j)∈E} x_{ij}E_{ij} ⪰ J.

By strong duality, we can also write:

ϑ(G) = max J • Y  (2)
subject to:  y_{ij} = 0  (i, j) ∈ E  (3)
I • Y = 1  (i.e. T r(Y) = 1)  (4)
Y ⪰ 0.  (5)

Lovász’s first definition of ϑ(G) was in terms of orthonormal representations. An orthonormal representation of G is a system v_{1}, ⋯, v_{n} of unit vectors in R^{n} such that v_{i} and v_{j} are orthogonal (i.e. v_{i}^{T} v_{j} = 0) whenever i and j are not adjacent. The value of the orthonormal representation is z = min_{c:||c||=1} max_{i∈V} \frac{1}{(c^{T} u_{i})^{2}} . This is easily seen to be an upper bound on α(G) (since ||c||^{2} ≥ ∑_{i∈S}(c^{T} u_{i})^{2} ≥ |S|/z for any stable set S). Taking the minimum value over all orthonormal representations of G, one derives another expression for ϑ(G). This result can be restated in a slightly different form. If x denotes the incidence vector of a stable set then we have that

∑_{i}(c^{T} v_{i})^{2}x_{i} ≤ 1.  (6)

In other words, the orthonormal representation constraints (6) are valid inequalities for ST AB(G), the convex hull of incidence vectors of stable sets of G. Grötschel et al. [10] show that if we let T H(G) = {x : x satisfies (6) and x ≥ 0}, then ϑ(G) = max{∑_{i} x_{i} : x ∈ T H(G)}. Yet more formulations of ϑ are known.

2.1 Perfect Graphs

A graph G is called perfect if, for every induced subgraph G′, its chromatic number is equal to the size of the largest clique in G′. Even though perfect graphs have been the focus of intense study, there are still important questions which are still open. The strong perfect graph conjecture of Berge claims that a graph is perfect if and only if it does not contain an odd cycle of length at least five or its complement. It is not even known if the recognition problem of deciding whether a graph is perfect is in P or NP-complete. However, the theta function gives some important characterizations (but not a “good” or NP∩co-NP characterization) of perfect graphs.

Theorem 1 (Grötschel et al. [10]) The following are equivalent:

• G is perfect,

• T H(G) = {x ≥ 0 : ∑_{i∈C} x_{i} ≤ 1 for all cliques C}

• T H(G) is polyhedral.

Moreover, even though recognizing perfect graphs is still open, one can find the largest stable set in a perfect graph in polynomial time by computing the theta function using semidefinite programming (Grötschel et al. [9, 11]); similarly one can solve the weighted problem, or find the chromatic number or the largest clique. Observe that if we apply this algorithm to a graph which is not necessarily perfect, we would either find the largest stable set or have a proof that the graph is not perfect.

Although ϑ(G) = α(G) for perfect graphs, ϑ(G) can provide a fairly poor upper bound on α(G) for general graphs. Feige [6] has shown the existence of graphs for which ϑ(G)/α(G) ≥ Ω(n^{1−ϵ}) for any ϵ > 0. See [7] for further details and additional references on the quality of ϑ(G).

3 The Maximum Cut Problem

Given a graph G = (V, E), the cut δ(S) induced by vertex set S consists of the set of edges with exactly one endpoint in S. In the NP-hard maximum cut problem (MAX CUT), we would like to find a cut of maximum total weight in a weighted undirected graph. The weight of δ(S) is w(δ(S)) = ∑_{e∈δ(S)} w_{e}. In this section, we describe an approach of the author and Williamson [8] based on semidefinite programming.

The maximum cut problem can be formulated as an integer quadratic program. If we let y_{i} = 1 if i ∈ S and y_{i} = −1 otherwise, the value of the cut δ(S) can be expressed as ∑_{(i,j)∈E} w_{ij} \frac{1}{2}(1 − y_{i}y_{j}). Suppose we consider the matrix Y = [y_{i}y_{j}]. This is a positive semidefinite rank one matrix with all diagonal elements equal to 1. Relaxing the rank one condition, we derive a semidefinite program giving an upper bound SDP on OP T:

SDP = max \frac{1}{2} ∑_{(i,j)∈E} w_{ij}(1 − y_{ij})  (7)
subject to:  y_{ii} = 1  i ∈ V
Y = [y_{ij}] ⪰ 0.

It is convenient to write the objective function in terms of the (weighted) Laplacien matrix L(G) = [l_{ij}] of G: l_{ij} = −w_{ij} for all i ≠ j and l_{ii} = ∑_{j} w_{ij}. For any matrix Y, we have L(G) • Y = ∑_{(i,j)∈E} w_{ij}(y_{ii} + y_{jj} − 2y_{ij}) (in particular, if Y = yy^{T} then we obtain the classical equality y^{T} L(G)y = ∑_{(i,j)∈E} w_{ij}(y_{i} − y_{j})^{2}). As a result, the objective function can also be expressed as \frac{1}{4}L(G) • Y.

The dual of this semidefinite program is SDP = \frac{1}{4} min\{∑_{j} d_{j} : diag(d) ⪰ L(G)}. This can also be rewritten as

SDP = \frac{1}{4}n min ; u:∑_{i} u_{i}=0 λ_{max}(L + diag(u)).  (8)

This eigenvalue bound was proposed and analyzed by Delorme and Poljak [4, 3]. In their study, they conjectured that the worst-case ratio OP T/SDP is 32/(25 + 5\sqrt{5}) ∼ 0.88445 for nonnegative weights and achieved by the 5-cycle. By exploiting (7), Goemans and Williamson [8] derived a randomized algorithm that produces a cut whose expected value is at least 0.87856 SDP, implying that OP T/SDP ≥ 0.87856 for nonnegative weights. We describe their random hyperplane technique and their elementary analysis below.

Consider any feasible solution Y to (7). Since Y admits a Gram representation, there exist unit vectors v_{i} ∈ R^{d} (for some d ≤ n) for i ∈ V such that y_{ij} = v_{i}^{T} v_{j}. Let r be a vector uniformly generated from the unit sphere in R^{d}, and consider the cut induced by the hyperplane {x : r^{T} x = 0} normal to r, i.e. the cut δ(S) where S = {i ∈ V : r^{T} v_{i} ≥ 0}. By elementary arguments, the probability that v_{i} and v_{j} are separated is precisely θ/π, where θ = arccos(v_{i}^{T} v_{j}) is the angle between v_{i} and v_{j}. Thus, the expected weight of the cut is exactly given by:

E[w(δ(S))] = ∑_{(i,j)∈E} w_{ij} \frac{arccos(v_{i}^{T} v_{j})}{π}.  (9)

Comparing this expression term by term to the objective function of (7) and using the fact that arccos(x)/π ≥ α\frac{1}{2}(1 − x) where α = 0.87856 ⋯, we derive that E[w(δ(S))] ≥ α\frac{1}{4}L(G) • Y. Hence if we apply the random hyperplane technique to a feasible solution Y of value ≥ (1 − ϵ)SDP (which can be obtained in polynomial time), we obtain a random cut of expected value greater or equal to α(1 − ϵ)SDP ≥ 0.87856 SDP ≥ 0.87856 OP T. Mahajan and Ramesh [19] have shown that this technique can be derandomized, therefore giving a deterministic 0.87856-approximation algorithm for MAX CUT.

The worst-case value for OP T/SDP is thus somewhere between 0.87856 and 0.88446, and even though this gap is small, it would be very interesting to prove Delorme and Poljak’s conjecture that the worst-case is given by the 5-cycle. This would however require a new technique. Indeed, Karloff [14] has shown that the analysis of the random hyperplane technique is tight, namely there exists a family of graphs for which the expected weight E[w(δ(S)] of the cut produced is arbitrarily close to α SDP.

No better approximation algorithm is currently known for MAX CUT. On the negative side though, Håstad [12] has shown that it is NP-hard to approximate MAX CUT within 16/17 + ϵ = 0.94117 ⋯ for any ϵ > 0. Furthermore, Håstad shows that if we replace the objective function by \frac{1}{2} ∑_{(i,j)∈E_{1}} w_{ij}(1 − y_{i}y_{j}) + \frac{1}{2} ∑_{(i,j)∈E_{2}} w_{ij}(1 + y_{i}y_{j}), then the resulting problem is NP-hard to approximate within 11/12 + ϵ = 0.91666 ⋯, while the random hyperplane technique still gives the same guarantee of α ∼ 0.87856.

The analysis of the random hyperplane technique can be generalized following an idea of Nesterov [21] for more general Boolean quadratic programs. First observe that (9) can be rewritten as E[w(δ(S))] = \frac{1}{2π} L(G) • arcsin(Y), where arcsin(Y) = [arcsin(y_{ij})]. Suppose now that we restrict our attention to weight functions for which L(G) ∈ K for a certain cone K. Then a bound of α would follow if we can show that L(G) • (\frac{2}{π} arcsin(Y)) ≥ L(G) • (αY) or L(G) • (\frac{2}{π} arcsin(Y) − αY ) ≥ 0. This corresponds to showing that (\frac{2}{π} arcsin(Y) − αY ) ∈ K^{∗}, where K^{∗} is the polar cone to K. For several interesting cones K (e.g. the cone of positive semidefinite matrices), this analysis can be performed.

We now describe a situation in which the semidefinite programming relaxation simplifies considerably. This is similar to the well-known LP bound in coding introduced by Delsarte [5] which corresponds to the theta function for graphs arising from association schemes. The results briefly sketched below were obtained jointly with F. Rendl.

Consider graphs whose adjacency matrix can be written as ∑_{i∈M} A_{i} where M ⊆ {1, ⋯, l} and A_{0}, A_{1}, ⋯, A_{l} are n × n 0 − 1 symmetric matrices forming an association scheme (see [2]):

1. A_{0} = I,

2. ∑_{i=0}^{l} A_{i} = J,

3. there exist p_{ij}^{k} (0 ≤ i, j, k ≤ l) such that A_{i}A_{j} = A_{j}A_{i} = ∑_{k=0}^{n} p_{ij}^{k}A_{k}.

When l = 2, the graph with incidence matrix A_{1} (or A_{2}) is known as a strongly regular graph.

We list below properties of association schemes, for details see for example [2]. Since the A_{i}’s commute, they can be diagonalized simultaneously and thus they share a set of eigenvectors. Furthermore, the (Bose-Mesner) algebra A generated by the A_{i}’s has a unique basis of minimal idempotents (i.e. E^{2} = E) E_{0}, ⋯, E_{l}. These matrices E_{i}’s are positive semidefinite (since their eigenvalues are all 0 or 1 by idempotence), and have constant diagonal equal to μ_{i}/n where μ_{i} is the rank of E_{i}.

For association schemes, we can show that the optimum correcting vector in (8) is u = 0, giving SDP = \frac{n}{4}λ_{max}(L(G)), and that the optimum primal solution Y is equal to nE_{p}/μ_{p} where p is the index corresponding to the eigenspace of the largest eigenvalue of L(G). To see this optimality, one simply needs to realize that Z = λ_{max}(L(G))I − L(G) can be expressed as ∑_{i≠p} c_{i}E_{i} and, as a result, satisfies complementary slackness with nE_{p}/μ_{p}: ZE_{p} = 0. Furthermore, if we were to add valid inequalities of the form C_{i} • Y ≤ b_{i} with C_{i} ∈ A to the primal semidefinite program then the primal and dual SDPs can be seen to reduce to a dual pair of linear programs:

\frac{1}{4} max ∑_{j}(L(G) • E_{j})x_{j} = \frac{1}{4} min ns + ∑_{i} b_{i}z_{i}
s.t.  ∑_{j} μ_{j}x_{j} = n  s.t.  μ_{j}s + ∑_{i}(C_{i} • E_{j})z_{i} ≥ L • E_{j} ∀j
∑_{j}(C_{i} • E_{j})x_{j} = b_{i} ∀i  z_{i} ≥ 0  ∀i
x_{j} ≥ 0  ∀j

The primal semidefinite solution is then ∑_{j} x_{j}E_{j} and the dual constraints imply that sI + ∑_{i} z_{i}C_{i} ⪰ L(G). As an illustration, the triangle inequalities can be aggregated in order to be of the required form, and thus the semidefinite program with triangle inequalities can be solved as a linear program for association schemes.

4 Deriving Valid Inequalities

Lovász and Schrijver [17, 18] have proposed a technique for automatically generating stronger and stronger formulations for integer programs. We briefly describe their approach here and discuss its power and its limitations.

Let P = {x ∈ R^{n} : Ax ≥ b, 0 ≤ x ≤ 1}, and let P_{0} = conv(P ∩ {0, 1}^{n}) denote the convex hull of 0 − 1 solutions. Suppose we multiply a valid inequality ∑_{i} c_{i}x_{i} − d ≥ 0 for P by either 1 − x_{j} ≥ 0 or by x_{j} ≥ 0. We obtain a quadratic inequality that we can linearize by replacing x_{i}x_{j} by a new variable y_{ij}. Since we are interested only in 0-1 solutions, we can impose that x_{i}^{2} = x_{i} for all i. Replacing x_{i} by y_{ii}, we therefore obtain a linear (“matrix”) inequality on the entries of Y. Let M(P) denote the set of all symmetric matrices satisfying all the matrix inequalities that can be derived in this way, and let N(P) = {x : Y ∈ M(P), x = Diag(Y)}, where Diag(Y) denotes the diagonal of Y; thus N(P) is a projection of M(P). By construction, we have that P_{0} ⊆ N(P) ⊆ P. They also consider a much stronger operator involving semidefinite constraints. Observe that, for any 0-1 solution x, the matrix Y defined above as xx^{T} must satisfy Y −Diag(Y)Diag(Y)^{T} = 0. This is again an (intractable) quadratic inequality but it can be relaxed to Y − Diag(Y)Diag(Y)^{T} ⪰ 0. Viewing Y − Diag(Y)Diag(Y)^{T} as a Schur complement, this is equivalent to

[ \begin{matrix}1 & Diag(Y)^{T} \\ Diag(Y) & Y \end{matrix} ] ⪰ 0.  (10)

As a result, defining M_{+}(P) as {Y ∈ M(P) satisfying (10)} and N_{+}(P) = {x : Y ∈ M_{+}(P), x = Diag(Y)}, we have that N_{0}(P) ⊆ N_{+}(P) ⊆ N(P) ⊆ P and optimizing a linear objective function over N_{+}(P) can be done via semidefinite programming.

Lovász and Schrijver study the operator N^{k}(·) (resp. N_{+}^{k}(·)) obtained by repeating N(·) (resp. N_{+}(·)) k times, and show that for any P ⊆ R^{n} we have N_{+}^{n}(P) = N^{n}(P) = N_{0}. Lovász and Schrijver show that the equivalence between (weak) optimization and (weak) separation [9, 11] implies that one can optimize (up to arbitrary precision) in polynomial time over N_{+}^{k} for any fixed value of k. They introduce the N-index (resp. N_{+}-index) of a valid inequality for P_{0} starting from P as the least k such that this inequality is valid for N^{k}(P) (resp. N_{+}^{k}(P)).

The N_{+}-index of an inequality can be much smaller than its N-index. The following theorem gives an upper bound on the N_{+}-index. The case k = 1 appears in [18], while the general case is unpublished by the author. Given a set Q ⊂ R^{n}, let Q[I] = {x ∈ Q : x_{i} = 1, i ∈ I}.

Theorem 2 Let a^{T} x ≤ a_{0} be a valid inequality for P with a ≥ 0. Let S = {i : a_{i} > 0}. Assume that a^{T} x ≤ a_{0} is valid for P [J] whenever (i) J ⊆ S, |J| = k and whenever (ii) J ⊆ S, |J| ≤ k − 1 and ∑_{j∈J} a_{j} ≥ a_{0}. Then a^{T} x ≤ a_{0} is valid for N_{+}^{k}(P).

The condition a ≥ 0 can be satisfied through complementation. This theorem essentially says that if one can derive validity of an inequality by fixing any set of k variables to 1, then we can derive it by k repeated applications of N_{+}; condition (ii) simply takes care of those sets of k variables that do not satisfy the inequality.

As an illustration, consider the stable set polytope where we can take as initial relaxation the fractional stable set polytope

F RAC(G) = {x : x_{i} + x_{j} ≤ 1 if (i, j) ∈ E, x_{i} ≥ 0 for all i ∈ V }.

Lovász and Schrijver [18] show that the N-index of a clique constraint on k vertices (∑_{i∈S} x_{i} ≤ 1) is k − 2 while its N_{+}-index is just 1, as can be seen from Theorem 2. Odd hole, odd antihole, odd wheel, and orthonormal representation constraints also have N_{+}-index equal to 1, implying the polynomial time solvability of the maximum stable set problem in any graph for which these inequalities are sufficient (including perfect graphs, t-perfect graphs, etc.).

However, there are also situations where the N_{+} operator is not very strong. Consider the matching polytope (the convex hull of incidence vectors of matchings, which can also be viewed as the stable set polytope of the line graph) and its Edmonds constraints: ∑_{i∈S} x_{i} ≤ (|S| − 1)/2 for |S| odd. Stephen and Tunçel [23] show that their N_{+}-index (starting from the relaxation with only the degree constraints) is exactly (|S| − 1)/2, and thus Θ(\sqrt{n}) iterations of N_{+} are needed to get the matching polytope where n is its dimension. Although n iterations are always sufficient for N or N_{+}, here is a situation in which not significantly fewer iterations are sufficient. Let

P = \{x ∈ R^{n} : ∑_{i∈S} x_{i} ≤ \frac{n}{2} for all S : |S| = \frac{n}{2} + 1\} .

Thus

P_{0} = \{x ∈ R^{n} : 0 ≤ x_{i} ≤ 1 for i = 1, ⋯, n, and ∑_{i=1}^{n} x_{i} ≤ \frac{n}{2}\} .

Let z^{k} and z_{+}^{k} denote max\{\frac{1}{n} ∑_{i=1}^{n} x_{i}\} over x ∈ N^{k}(P) and N_{+}^{k}(P), respectively. Goemans and Tunçel (unpublished) have obtained recurrences for z^{k} and z_{+}^{k} and derived several properties; their most important results are summarized below.

Theorem 3 1. For k ≤ \frac{n}{2}, z^{k} ≥ z_{+}^{k} > \frac{n/2−r}{n/2+1−r}. In particular z^{n/2−1} > 0.5.

2. For k ≤ \frac{n}{2} − \sqrt{n} + \frac{3}{2}, we have z^{k} = z_{+}^{k}.

Together with Theorem 2, (i) implies that the N_{+}-index of ∑_{i=1}^{n} x_{i} ≤ n/2 is exactly n/2, while one can show that its N-index is n − 2. Furthermore, (ii) says that semidefinite constraints do not help for n/2 − o(n) iterations.

References

[1] F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Opt., 5:13–51, 1995.

[2] A.E. Brouwer and W.H. Haemers. Association schemes. In Handbook of Combinatorics, R.L. Graham, M. Grötschel and L. Lovász, eds, Elsevier, 747–771, 1995.

[3] C. Delorme and S. Poljak. Combinatorial properties and the complexity of a max-cut approximation. Europ. J. Comb., 14:313–333, 1993.

[4] C. Delorme and S. Poljak. Laplacian eigenvalues and the maximum cut problem. Math. Prog., 62:557–574, 1993.

[5] P. Delsarte. An algebraic approach to the association schemes of coding theory. Philips Research Reports, Supplement, 10, 1973.

[6] U. Feige. Randomized graph products, chromatic numbers, and the Lovász θ-function. In Proc. of the 27th ACM Symp. on Theory Comput., pages 635– 640, 1995.

[7] M.X. Goemans. Semidefinite programming in combinatorial optimization. Math. Prog., 79:143–161, 1997.

[8] M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42:1115–1145, 1995.

[9] M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169–197, 1981.

[10] M. Grötschel, L. Lovász, and A. Schrijver. Relaxations of vertex packing. JCT B, pages 330–343, 1986.

[11] M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin, 1988.

[12] J. Håstad. Some optimal inapproximability results. In Proc. of the 29th ACM Symp. on Theory Comput., 1997.

[13] R. Horn and C. Johnson. Matrix Analysis. Cambridge University Press, 1985.

[14] H. Karloff. How good is the Goemans-Williamson MAX CUT algorithm. In Proc. of the 28th ACM Symp. on Theory Comput., pages 427–434, 1996.

[15] D. Knuth. The sandwich theorem. Elec. J. Comb., 1, 1994.

[16] L. Lovász. On the Shannon capacity of a graph. IEEE Trans. Inform. Th., IT-25:1–7, 1979.

[17] L. Lovász and A. Schrijver. Matrix cones, projection representations, and stable set polyhedra. In Polyhedral Combinatorics, volume 1 of DIMACS series in Disc. Math. and Theor. Comp. Sci., pages 1–17. AMS, 1989.

[18] L. Lovász and A. Schrijver. Cones of matrices and setfunctions, and 0-1 optimization. SIAM J. Opt., 1:166–190, 1991.

[19] S. Mahajan and H. Ramesh. Derandomizing semidefinite programming based approximation algorithms. In Proc. 36th Symp. on Found. of Comp. Sci., pages 162–169, 1995.

[20] B. Mohar and S. Poljak. Eigenvalue methods in combinatorial optimization. In R. Brualdi, S. Friedland, and V. Klee, editors, Combinatorial and Graph-Theoretic Problems in Linear Algebra, volume 50 of The IMA Volumes in Mathematics and its Applications, pages 107–151. Springer-Verlag, 1993.

[21] Y. Nesterov. Quality of semidefinite relaxation for nonconvex quadratic optimization. CORE Discussion Paper 9719, Louvain-La-Neuve, Belgium, 1997.

[22] Y. Nesterov and A. Nemirovskii. Interior Point Polynomial Methods in Convex Programming. SIAM, Philadelphia, PA, 1994.

[23] T. Stephen and L. Tunçel. On a representation of the matching polytope via semidefinite liftings. Unpublished, 1997.

[24] L. Vandenberghe and S. Boyd. Semidefinite programming. SIAM Rev., pages 49–95, 1996.

Michel X. Goemans

M.I.T. and University of Louvain Mailing address: CORE, 34 Voie du Roman Pays B-1348 Louvain-La-Neuve Belgium goemans@core.ucl.ac.be