Computational Complexity of Convex Bodies

THE COMPUTATIONAL COMPLEXITY OF CONVEX BODIES 2006 Abstract. We discuss how well a given convex body B in a real d-dimensional vector space V can be approximated by a set X for which the membership question: “given an x ∈ V , does x belong to X?” can be answered efficiently (in time polynomial in d). We discuss approximations of a convex body by an ellipsoid, by an algebraic hypersurface, by a projection of a polytope with a controlled number of facets, and by a section of the cone of positive semidefinite q uadratic f orms. We i llustrate s ome of the results on the Traveling Salesman Polytope, an example of a complicated convex body studied in combinatorial optimization. 1. Introduction Let V be a finite-dimensional r eal vector space. A s et B ⊂ V i s c alled c o nvex if for every two points x, y ∈ B the interval [x, y] = αx + (1 − α)y : 0 ≤ α ≤ 1 also lies in B. A convex set B ⊂ V is a convex body if B is compact with a non-empty interior. Various notions of complexity for convex bodies have been discussed from a variety of points of view, see, for example, [Sz06] for a recent survey. In this paper, we suggest the following general approach to the computational complexity of convex bodies. Let B ⊂ V be a d-dimensional convex body. We would like to design an efficient algorithm for the following membership problem (1.1) The membership problem for B Input: A point x ∈ V . Output: “Yes” if x ∈ B and “No” if x ∈ / B. Key words and phrases. convex body, computational complexity, linear programming, semidefinite programming, Traveling Salesman Polytope. 1 The algorithm in Problem 1.1 is, of course, determined by the convex body B. It is important to note that we do not count the time and resources spent on creating such an algorithm towards the computational complexity of B. Once the algorithm is created, only the time needed to answer the question whether a given point x ∈ V belongs to B counts as the complexity of B. At this point, it is not important to us what model of computation we use. For example, we can identify V = Rd and assume that a point x = (ξ1 , . . . , ξd ) is given by its real coordinates. The algorithm employs arithmetic operations and its complexity is the number of operations used (the real model). Alternatively, we may assume that the point x has rational coordinates and count bit operations instead (the bit model). We are interested in how the complexity of the algorithm depends on the dimension d. The algorithmic theory of convexity, see [G+93], implies that as soon as there is a polynomial time algorithm in the Membership Problem 1.1 for a convex body B (in the bit model), there is a polynomial time algorithm in the problem of optimizing a given linear function on B (again, in the bit model). Hard optimization problems supply a variety of convex bodies for which the membership problem is likely to be hard. We concentrate on one model example, the (symmetric) Traveling Salesman Polytope. (1.2) Example: the Traveling Salesman Polytope. Let us fix an integer n ≥ 4. In the space Matn of n×n real matrices, we define T SPn as the convex hull of the adjacency matrices of the Hamiltonian cycles in a complete graph on n vertices. That is, for any Hamiltonian cycle C (a cycle that visits every vertex exactly once) of a complete undirected graph on the vertices {1, . . . , n}, we introduce the n × n matrix x = x(C) where  xij = 1 if ij is an edge of C 0 otherwise and take the convex hull of all such matrices x(C). One can observe that T SPn has (n − 1)!/2 vertices and that dim T SPn = (n2 − 3n)/2, see Chapter 58 of [Sc03]. We define the ambient space Vn as the affine hull of T SPn with the origin at the center a = (aij ), where  2 if i 6= j aij = n 0 if i = j The space Vn consists of the n × n symmetric matrices with zeros on the diagonal and the row and column sums equal to 2. The facial structure of T SPn was studied in many papers but still remains a mystery, see Chapter 58 of [Sc03] for a survey. In some sense, unless the complexity hierarchy collapses, the facets of T SPn cannot be described. More precisely, there can be no algorithm of a polynomial in n complexity, which, given an inequality in Vn decides whether it defines a facet of T SPn , see Chapter 4 of [Sc03]. 2 Since the Membership Problem 1.1 can be quite hard, we also consider the computational complexity of the approximation problem: we want to find a set X ⊂ V approximating B such that the membership problem for X can be solved within a given complexity, preferably in time polynomial in dim V . (1.3) Measuring the quality of approximation In many important cases, the convex body B is symmetric, that is B = −B and we measure how well X approximates B by a number α ≥ 1 such that X ⊂ B ⊂ αX. Often, B is not symmetric but has a natural center nevertheless, as in the case of the Traveling Salesman Polytope. In such a case, taking the center of B for the origin, we measure the quality of approximation in the same way. In many cases, but not in all, the set X is convex as well. This paper is meant to be a survey although it contains some new results, mostly in Section 5 and in Theorems 4.6 and 6.2. The paper is structured as follows. In Section 2, we discuss how well a symmetric convex body can be approximated by an ellipsoid, or, more generally, by an algebraic hypersurface of a given degree. In particular, for any  > 0 and any √ symmetric convex body B we obtain a set X such that X ⊂ B ⊂ αX for α =  dim B and the membership problem for X can be solved in time polynomial in dim B. In Section 3, we review results on approximation of convex bodies by polytopes with a controlled number of vertices or facets. We show that to approximate a d-dimensional symmetric convex body within a constant factor, it is sufficient to take a polytope with eO(d) vertices. The exponential in d number of vertices is also necessary in the worst case, as shows the example of the Euclidean ball. In Section 4, we discuss approximations of convex bodies by projections of polytopes with a controlled number of facets. Note that if X is a projection of a polytope with N facets then the membership problem for X is a linear programming problem that can be solved in time polynomial in N (in the bit model), cf. [G+93]. On the other hand, the number of facets of a polytope can grow exponentially if the operation of projection is applied, so potentially we get more flexibility for approximation. We describe several interesting phenomena here. First, we show that to obtain a good approximation of a symmetric convex body by a projection of a polytope with not too many facets, we may have to require the polytope to be non-symmetric. This is the case, for example, when the body is the cross-polytope (octahedron). Then we discuss an amazing approximation, constructed by A. Bend Tal and A. Nemirovski [BN01] of the Euclidean ball in
R within a factor of (1 + ) −1 by the projection of a polytope with only O d ln  facets. Finally, we discuss a general way to approximate an arbitrary convex body by a projection of a polytope 3 with a controlled number of facets. As an illustration, we state the result of the second author that for any  > 0 the Traveling Salesman Polytope T SPn can be approximated within a factor of n by the projection of a polytope with nO(1/) facets. In Section 5, we present a construction which, for any d-dimensional convex body B ⊂ V “almost approximates” its polar B ◦ ⊂ V ∗ by a section of a polytope √ with not more than eO( d ln d) vertices. We consider V ∗ embedded into the√space C(B) of continuous functions on B, construct a polytope R ⊂ C (B) with eO( d ln d) vertices and show that we obtain a good approximation of B ◦ if we slightly “bend” V ∗ ⊂ C(B) and intersect in with R. In Section 6, we discuss approximations by a section of the cone of positive semidefinite quadratic forms. Such approximations also lead to efficient algorithms for the membership problem. We review by now classic results on approximations of the cut polytope and its variations. We also present a general construction and illustrate it by the result of the second author that the polar T SPn◦ of the Traveling Salesman Polytope can be approximated within a factor of n by a section of the cone of positive semidefinite quadratic forms in nO(1/) variables. 2. Approximation by algebraic hypersurfaces An ellipsoid E ⊂ V is a set defined as n o E = v ∈ V : q(v − v0 ) ≤ 1 , where q : V −→ R is a positive definite quadratic form and v0 ∈ V is a particular point called the center of the ellipsoid. As is known, see for example, [Ba97], for any convex body B ⊂ V there is a unique ellipsoid E ⊂ B that has the largest volume among all ellipsoids contained in B. It is called the John ellipsoid of B and it satisfies E ⊂ B ⊂ dE, where d = dim V and the origin of V is moved to the center of E. If B is symmetric then the John ellipsoid E is necessarily centered at the origin and satisfies √ E ⊂ B ⊂ dE. For the Traveling Salesman Polytope T SPn the ellipsoid E is centered at the center of T SPn , touches the facets of T SPn defined by the equations xij = 0 and satisfies √ (n − 3) n E ⊂ T SPn ⊂ E for n ≥ 5, 2 see [BB05]. Since an ellipsoid E is defined by
one quadratic inequality, the membership problem for E can be solved in O d2 time for d = dim V . One can ask whether better bounds can be obtained by using polynomial inequalities of higher order. For symmetric convex bodies such a result was obtained in [Ba03]. We state some general prerequisites first. 4 (2.1) Symmetric convex bodies and norms. Polarity. With a symmetric convex body B ⊂ V one naturally associates a norm k · kB on V defined by n kvkB = inf λ > 0 : o v ∈ λB . Approximating B by an efficiently computable set X is equivalent to approximating k · kB by an efficiently computable function f . Let V ∗ be the space of all linear functions ` : V −→ R. We recall that the polar ◦ B ⊂ V ∗ of a convex body B ⊂ V is defined by n B = `∈V∗ : ◦ `(v) ≤ 1 for all o v∈B . ◦ The standard duality result states that (B ◦ ) = B if B is a closed convex set containing the origin. The following result was proved in [Ba03]. (2.2) Theorem. For any symmetric convex body B ⊂ V and any integer k ≥ 1 there exists a homogeneous polynomial p : V −→ R such that p is the sum of squares of homogeneous polynomials of degree k and p1/2k (v) ≤ kvkB ≤ α(d, k)p1/2k (v) for all v ∈ B, where  α(d, k) = d+k−1 k 1/2k and d = dim B. In other words, the set n X= v∈V : o p(v) ≤ 1 approximates B within a factor of α(d, k). Note that the membership problem for
2k time. If d  k  1, applying Stirling’s formula, we get X can be solved in O d √ α(d, k) ≈ d 1/2k (k!) r ≈ de . k It follows then that for any fixed  > 0 √ we can choose k = k() large enough so that X approximates B within a factor of  dim B and the membership problem for X can be solved in time polynomial in dim B. It is not clear whether the set X can always be chosen convex, although this is the case in many situations. 5 Sketch of proof of Theorem 2.2. Let V ∗ be the dual space of all linear functionals ` : V −→ R and let B ◦ = {` ∈ V ∗ : `(v) ≤ 1 for all v ∈ B} be the polar of B. By the standard duality argument, we can write n o ◦ kvkB = max `(v) : ` ∈ B . Let V ⊗k be the tensor product of k copies of V , so V ⊗k kvkkB n
= max `⊗k v ⊗k : ⊗k = (V ∗ ) . Then o `∈B . ◦ ⊗k Now, let us define a symmetric convex set C ⊂ (V ∗ ) Then
∗ as the convex hull  C = conv `⊗k , −`⊗k :  ` ∈ B◦ . n
kvkkB = max L v ⊗k : o L∈C . Finally, we approximate C by an ellipsoid E ⊂ C. The crucial consideration is that ⊗k since C lies in the symmetric part of (V ∗ ) , we have  dim C ≤ dim V + k − 1 k  and hence E approximates C within a factor of αk (d, k). It remains to notice that the formula n o p
p(v) = max L v ⊗k : L ∈ E indeed defines a polynomial p : V −→ R of degree 2k which is a sum of squares of polynomials of degree k.  There are several open questions related to Theorem 2.2. (2.3) The best approximation? Suppose that we want to approximate an arbitrary norm kvkB by an expression p1/2k (v), where p : V −→ R is a homogeneous polynomial of degree 2k. Is the coefficient α(d, k) of Theorem 2.2 best that we can get? This is so in the case of k = 1, since the d-dimensional cube n o Id = (ξ1 , . . . , ξd ) : |ξi | ≤ 1 for i = 1, . . . , d 6 or the d-dimensional cross-polytope (octahedron) n Od = (ξ1 , . . . , ξd ) : d X o |ξi | ≤ 1 i=1 √ cannot be approximated by an ellipsoid better than within a factor of d, cf. [Ba97]. Similarly, in the non-symmetric situation, the d-dimensional simplex n ∆d = (ξ1 , . . . , ξd+1 ) : d+1 X ξi = 1 and ξi ≥ 0 o for i = 1, . . . , d + 1 i=1 cannot be approximated by an ellipsoid better than within a factor of d. For k > 1 it is not clear whether the bound of Theorem 2.2 is optimal. One can show, however, that the octahedron Od cannot be approximated by a hypersurface √ of degree 4 or 6 better than within a certain factor c d for some absolute constant c > 0 [Ba03]. The idea of the proof is as follows. Once a convex body B and the degree 2k are fixed, there exists the best approximating polynomial p. Furthermore, the polynomial p can be chosen to be invariant under the group of the symmetries of B. In the case of Od , it follows that one can choose p to be a symmetric polynomial in ξ12 , . . . , ξd2 , from which the estimate can be deduced. It is interesting to note that while the cube Id and the octahedron Od demonstrate similar behavior with respect to ellipsoidal approximations, their behavior with respect to higher degree approximations very much differ. Indeed, the cube Id can be approximated by a hypersurface of degree 2k within a factor of d1/2k . For that, one can choose p(x) = d X ξi2k for x = (ξ1 , . . . , ξd ) . i=1 (2.4) Convex approximation? Although in many special cases the function p1/2k (·) constructed in Theorem 2.2 turns out to be a norm, there is no reason to believe that it is always a norm (but there are no explicit counterexamples either). Equivalently, there is no apparent reason why the set n o X = v ∈ V : p(v) ≤ 1 should be convex. It is an interesting question whether one can choose p to be a norm and still get the same order of approximation. One natural candidate would be Z (2.4.1) p(v) = `2k (v) dµ(`), B◦ 7 where µ is a certain probability measure on the polar B ◦ . One can show that for the normalized Lebesgue measure µ the bounds generally are much weaker than those of Theorem 2.2. A natural candidate is the exterior angle measure defined as follows. Let Sd−1 ⊂ Rd be the unit sphere in Euclidean space Rd endowed with the scalar product hi and let ν be the Haar probability measure on Sd−1 . Let K ⊂ Rd be a convex body. For a closed subset X ⊂ K, let us define n o d−1 µK (X) = ν c ∈ S : maxhc, xi = maxhc, xi . x∈X x∈K In words: the measure of a closed subset X is the proportion of linear functions of length 1 that attain their maximum on K at a point x ∈ X. Clearly, the probability measure µK depends on the convex body K as well as on the Euclidean structure in Rd . Although no bounds have been proved, it seems plausible that by choosing a scalar product in V in which the John ellipsoid E of B is the unit ball and letting µ = µB ◦ in (2.4.1), one obtains a norm p1/2k which gives a similar order approximation as in Theorem 2.1. 3. Approximations by polytopes Any convex body B ⊂ V can be arbitrarily well approximated by the convex hull of a sufficiently large finite subset X ⊂ B. Consequently, the membership problem for B is replaced by the membership problem for the polytope P = conv(X) whose complexity (in the bit model) is polynomial in the cardinality |X| of X. In the dual setting, any convex body can be arbitrarily well approximated by the intersection of a sufficiently large set X of halfspaces. Then the complexity of the membership problem is linear in |X| in both the real and the bit models. How large should X ⊂ B be so that conv(X) approximates B reasonably well? The following result is well-known, see for example, Lemma 4.10 of [Pi89]. (3.1) Lemma. Let B ⊂ V be a symmetric convex body. Then, for any 1 >  > 0 there is a subset X ⊂ B such that  d |X| ≤ 2 1+  P ⊂B⊂ 1 P 1− and for for d = dim V P = conv(X). Proof. Let k · kB be the norm associated with B, see Section 2.1. Let X ⊂ B be a maximal (under inclusion) subset such that kx1 − x2 kB >  for all distinct x1 , x2 ∈ X. 8 Since X is maximal, for every x ∈ B there is a point y ∈ X and a point z ∈ B such that x − y = z. In other words, B ⊂ X + B ⊂ P + B. Iterating, we get B ⊂ P + P + 2 P + . . . + k P + k+1 B and taking the limit we conclude that B⊂ 1 P. 1− Next, we estimate the number of points in X. We notice that       x1 + B ∩ x2 + B = ∅ for distinct x1 , x2 ∈ X. 2 2 Furthermore, [      x+ B ⊂ 1+ B. 2 2 x∈X Hence     vol 1 + B , B ≥ |X| vol 2 2 from which  |X| ≤ 2+  d as required.  Although in many cases the bound can be slightly sharpened, the bottom line is that the bound on the number |X| of points is exponential in the dimension. In fact, simple volume estimates show that even if B ⊂ Rd is the Euclidean ball, the number of points needed to approximate B within a constant factor is exponentially large in d. The following result is proved, for example, in [Ba97]. (3.2) Theorem. Let B ⊂ Rd be the unit ball and let X ⊂ B be a set such that for P = conv(X) we have P ⊂ B ⊂ αP. Then  |X| ≥ exp d 2α2  . Similarly, if P is the intersection of a set X of halfspaces such that P ⊂ B ⊂ αP then  |X| ≥ exp 9 d 2α2  . 4. Approximation by projections Let B ⊂ V be a convex body. Suppose that we manage to construct a polytope P ⊂ W , where W is some other vector space, and a linear transformation T : W −→ V such that the image Q = T (P ) approximates B reasonably well. Given an x ∈ V , testing whether x ∈ Q reduces to testing whether the affine subspace T −1 (x) has a non-empty intersection with P , which is a linear programming problem. In particular, if P is defined by N linear inequalities, the complexity of the membership problem for Q is bounded by a polynomial in N (in the bit model). On the other hand, the number of facets of Q can be exponentially large in N , which shows that, in principle, Q may provide a fairly good approximation even to rather “nonpolytopal” convex bodies B. In the dual setting, we are interested in approximating the body B by a section of a polytope. Namely, we want to construct a vector space W ⊃ V and a polytope P ⊂ W such that the intersection Q = P ∩ V approximates B reasonably well. If P is defined as the convex hull of N vertices, the membership problem for P , being a linear programming problem, has the complexity that is polynomial in N (in the bit model). On the other hand, the number of vertices of Q = P ∩ V can be exponentially large in N , which, in principle, can lead to good approximations of B. One can observe that a polytope Q is a projection of a polytope with at most N facets if and only if Q is a section of a polytope with at most N vertices, so the two approaches are essentially identical. (4.1) Good sections are good projections and vice versa. Let V ⊂ W be a pair of spaces, let P ⊂ W be a polytope with N vertices and let Q = P ∩ V . Since P has N vertices, there exists a simplex ∆ ⊂ RN , see Section 2.3, and a linear transformation T : RN −→ W such that P = T (∆). Then U = T −1 (V ) ⊂ RN is a subspace, the polytope P 0 = ∆ ∩ U has at most N facets and Q = T (P 0 ). In other words, a polytope that is a section of a polytope with at most N vertices can be represented as a projection of a polytope with at most N facets. Vice versa, let P ⊂ W be a polytope with N facets, let T : W −→ V be a linear transformation and let Q = T (P ). Fixing a scalar product in W , we identify V with a subspace V ⊂ W and T with the orthogonal projection of W onto V . Assuming that P contains the origin in its interior, let us consider the polars P ◦ and Q◦ . One can see that Q◦ = P ◦ ∩ V . Since P ◦ is a polytope with N vertices, by the above reasoning Q◦ can be represented as a projection of a polytope with ◦ at most N facets. Dualizing again and using that (Q◦ ) = Q, we conclude that Q can be represented as a section of a polytope with at most N vertices. Approximations by projections are well suited for taking intersections and direct products. (4.2) Operations on projections. 10 For i = 1, 2, let Pi ⊂ Wi be polyhedra, let Ti : Wi −→ V be linear transformations, and let Qi = Ti (Pi ). Let Q = (Q1 ∩ Q2 ) ⊂ V . We observe that Q is the image of the polyhedron P ⊂ W1 ⊕ W2 , n o P = (x1 , x2 ) : x1 ∈ P1 , x2 ∈ P2 , and T1 (x1 ) = T2 (x2 ) under the linear transformation defined by T (x1 , x2 ) = T1 (x1 ). If Pi has at most Ni facets for i = 1, 2 then P has at most N = N1 + N2 facets. For i = 1, 2, let Pi ⊂ Wi be polyhedra, let Ti : Wi −→ Vi be linear transformations, and let Qi = Ti (Pi ). Let Q = (Q1 × Q2 ) ⊂ V1 ⊕ V2 . Then Q is the image of the polyhedron P = (P1 × P2 ) ⊂ W1 ⊕ W2 under the linear transformation defined by T (x1 , x2 ) = (T1 (x1 ) , T2 (x2 )). Similarly, if Pi has at most Ni facets for i = 1, 2 then P has at most N = N1 + N2 facets. One interesting feature of approximations by sections and projections is that it breaks symmetry. Namely, to obtain a sufficiently close approximation of a symmetric convex body B by a projection of a polytope P with not too many facets, we may have to choose the polytope P to be non-symmetric. Let Od ⊂ Rd be the standard octahedron (cross-polytope), see Section 2.3. Clearly, Od has 2d vertices and hence there is a simplex ∆2d−1 ⊂ R2d with 2d vertices and a linear transformation T : R2d −→ Rd such that T (∆2d−1 ) = Od . In other words, Od can be represented as the projection of a polytope with 2d facets. Suppose, however, that we want to construct a symmetric polytope P ⊂ W and a linear transformation T : W −→ Rd such that Q = T (P ) approximates Od within a factor of 2. One can show that the number N of facets of P has to be exponentially large in d. (4.3) Theorem. Let Od ⊂ Rd be the cross-polytope d n o X Od = (ξ1 , . . . , ξd ) : |ξi | ≤ 1 i=1 and suppose that P ⊂ W is a symmetric polytope with N facets and T : W −→ Rd is a linear transformation such that Q ⊂ Od ⊂ 2Q for Q = T (P ). Then N ≥ ecd for some absolute constant c > 0. Proof. The proof uses the notion of the type 2 constant of a Banach space, see [Pi89] and [To89]. Let V be a finite-dimensional vector space, let B ⊂ V be a symmetric convex body and let k · kB be the corresponding norm. The type 2 constant of B is the 11 smallest number κ = κ(B) > 0 such that for any set of vectors x1 , . . . , xm ∈ V we have m m X X 2 ≤ κ2 (B) E i xi kxi k2B , B i=1 i=1 where the expectation is taken with respect to independent random signs i :  i = 1 with probability −1 with probability 1 2 1 2. One can observe that κ(B) = 1 if B is the unit ball in some Euclidean metric and that if T : V −→ W is an invertible linear transformation then κ(B) = κ (T (B)) for any symmetric convex body B ⊂ V . Since every convex body can be approximated by an ellipsoid, it follows that κ(B) exists (in particular, is finite) for all symmetric convex bodies B. Let B ⊂ W be a symmetric convex body and let U ⊂ W be a subspace. It is immediate that κ (B ∩ U ) ≤ κ(B). (4.3.1) Furthermore, suppose that T : W −→ V is a linear surjection. Then
κ T (B) ≤ κ(B). (4.3.2) To prove (4.3.2), we notice that kT ykT (B) ≤ kykB for all y∈W and that for every x ∈ V there is y ∈ W such that T (y) = x and kykB = kxkT (B) . To establish (4.3.2), let us choose any x1 , . . . , xm ∈ V and then y1 , . . . , ym ∈ W such that T (yi ) = xi and kyi kB = kxi kT (B) for i = 1, . . . , m. Then E m X i=1 2 i xi ≤E T (B) m X 2 i yi i=1 2 ≤ κ (B) B X i=1 and the proof of (4.3.2) follows. 12 kyi k2B 2 = κ (B) m X i=1 kxi k2T (B) Suppose now that P is a symmetric polytope with N facets. Then, up to a linear transformation, P can be represented as a section of an N -dimensional cube IN , see Section 2.3. Hence κ(P ) ≤ κ (IN ) and if Q is a projection of P , we have κ(Q) ≤ κ(P ) ≤ κ (IN ) . Furthermore, under the conditions of the theorem, we have κ (Od ) ≤ 2κ(Q) ≤ 2κ (IN ) . On the other hand, one can show that √ √ κ (Od ) ≥ d and κ(IN ) ≤ c ln N for some absolute constant c > 0, see Section 4 of [To89]. This proves that N has to be exponentially large in d.  Theorem 3.2 shows that the d-dimensional Euclidean ball is not approximated very well by a polytope with a subexponential in d number of vertices or facets. The situation changes radically if we consider approximations by a projection of a polytope with a small number of facets or by a section of a polytope with a small number of vertices. For example, the intersection of a 2d-dimensional octahedron O2d with a random d-dimensional subspace of R2d approximates the d-dimensional Euclidean ball within an absolute constant, see, for example, [Ba97]. The results of [B+89] on approximation
of zonoids by zonotopes imply that for any d and  > 0 there is an N = O∗ d−2 , where ∗ stands for some logarithmic factors, and a linear transformation T : RN −→ Rd , such that the image T (IN ) of the cube IN ⊂ RN approximates the unit ball B ⊂ Rd within a factor of (1 + ). Note that in this case we approximate a symmetric convex body by the projection of a symmetric polytope. A. Ben-Tal and A. Nemirovski
[BN01] provide a remarkable construction of a polytope P with N = O d ln −1 of facets whose projection T (P ) approximates Euclidean ball B ⊂ Rd within a factor of (1 + ). We sketch the construction below. Unlike in the case of zonotopal approximation of [B+89], the polytope P is not symmetric. (4.4) A tight approximation of the Euclidean ball by a projection. Let n Bd = (ξ1 , . . . , ξd ) : d X ξi2 o ≤1 i=1 be the d-dimensional unit ball. The first idea of [BN01] is to reduce the general case to that of d = 2. Let us consider the (d + 1)-dimensional round cone n Cd = (ξ1 , . . . , ξd ; τ ) : d X i=1 13 ξi2 ≤ τ 2 o and τ ≥ 0 . One can observe that a close approximation of Cd by a projection of a polyhedron with at most N facets results in a close approximation of Bd by a projection of a polytope with at most N facets and vice versa. Let us write d = r + b for some positive integers r and b and let us consider the corresponding round cones of lower dimensions: r X n Cr = (ξ1 , . . . , ξr ; ρ) : i=1 r X n Cb = (η1 , . . . , ηb ; β) : ξi2 ≤ ρ2 o and ρ ≥ 0 and ηi2 ≤ β 2 o and β ≥ 0 . i=1 In the space Rd+3 with the coordinates ξ1 , . . . , ξb ; η1 , . . . , ηr ; ρ, β, τ we consider the subset n X = (ξ1 , . . . , ξr ; η1 , . . . ηb ; ρ, β, τ ) : r X ξi2 2 ≤ρ , b X ηi2 ≤ β 2 , ρ2 + β 2 ≤ τ 2 and i=1 i=1 o ρ, β, τ ≥ 0 . Clearly, Cd is the image of X under the projection which forgets ρ and β. On the other hand, we have
X = (Cr × Cb × Vτ ) ∩ C2 × Vξ,η , where n C2 = (ρ, β, τ ) : 2 2 β +ρ ≤τ 2 o and ρ, β, τ ≥ 0 is the “quarter” of the 3-dimensional round cone and Vτ and Vξ,η are the appropriate coordinate subspaces. Using the operations of direct product and intersection, see Section 4.2, one can show that good approximations of Cr , Cb , and C2 by projections of polyhedra leads to a good approximation of Cd by a projection of a polyhedron. Essentially, the problem boils down to an efficient approximation of the quarter of the disc: n o 2 2 B2 = (ξ, η) : ξ + η ≤ 1 and ξ, η ≥ 0 . For that, A. Ben-Tal and A. Nemirovski provide the following ingenious construction. Let us define the sequence of transformations Rn of R2 by π π + η sin n n 2 2 π π 0 η = − ξ sin n + η cos n . 2 2 14 ξ 0 = ξ cos Geometrically, Rn is a clockwise rotation through an angle of π/2n followed by the reflection in the ξ-axis if the obtained point lies in the lower halfplane. If we pick a point z = (ξ, η) with ξ, η ≥ 0 and apply the sequence of transformations R2 , R3 , R4 , . . . , then the resulting sequence of points has its limit on the interval 0 ≤ ξ ≤ 1, η = 0 if and only if z ∈ B2 . Let us choose a positive integer m. In the space of variables ξk , ηk for k = 1, . . . , m we define the polyhedron Pm by the equations and inequalities π π + ηk−1 sin k k 2 2 π π ηk ≥ −ξk−1 sin k + ηk−1 cos k 2 2 π π ηk ≥ ξk−1 sin k − ηk−1 cos k for k = 2, . . . , m 2 2 ξk = ξk−1 cos and ξ1 , η1 ≥ 0, 0 ≤ ξm ≤ 1, ηm ≤ π . 2m The projection of Pm onto the coordinates (ξ1 , η1 ) approximates B2 within an error exponentially small in m. (4.5) A general approximation construction. Let B ⊂ Rd be a convex body we want to approximate by a projection of a polytope with at most N facets, or, equivalently, by a section of a polytope with at most N vertices. Here is a general construction. Without loss of generality, we assume that B contains the origin in its interior and hence we may view B as the polar of its own polar B ◦ ⊂ Rd . Next, we approximate B ◦ by a sufficiently dense finite subset X ⊂ B ◦ so that X ◦ approximates B well enough. Let us consider the space RX of all functions f : X −→ R and let A ⊂ RX be the affine subspace of all affine functions f : X −→ R whose average value on X is 1. In other words, A consists of the functions of the type f (x) = hc, xi + α for some c ∈ Rd and α ∈ R such that, additionally, 1 X f (x) = 1. |X| x∈X It is not hard to see that X ◦ can be viewed as n o X ◦ = f ∈ A : f (x) ≥ 0 for all x ∈ X . For a subset Y ⊂ X let δY ∈ RX be the indicator of Y , that is  δY (x) = 1 if x ∈ Y 0 if x ∈ / Y. 15 We write simply δx instead of δ{x} . Now we can write X ◦ = A ∩ co (δx : x ∈ X) , where “co” stands for the conic hull of the set, that is, the set of all non-negative linear combinations of the elements of the set. Let us choose a family F ⊂ 2X . We define the approximation of BF as BF = A ∩ co (δF : F ∈ F) . Clearly, BF is the intersection of an affine subspace with a polyhedron with at most |F| vertices. One can expect that the finer F gets, the better approximation BF to B we obtain. For example,  we maychoose X as the intersection of B with a d sufficiently dense grid, X = B ∩ (Z) and then choose Fk consisting of the sets of points lying on an affine
coordinate subspace of codimension k. Generally, we will have |Fk | = O dk −k . Using this approach, the second author was able to obtain the following approximation result for the Traveling Salesman Polytope T SPn , see Example 1.2. (4.6) Theorem. Let us choose an  > 0 and let Vn be the ambient space of T SPn .
Then there exists a polytope Pn ⊂ Wn with at most N = O n4/ facets and a linear transformation T : Wn −→ Vn such that for Qn = T (Pn ) one has Qn ⊂ T SPn ⊂ (n)Qn . The proof of Theorem 4.6 is rather technical and will be presented elsewhere. (4.7) Remarks and open questions. Given a series of combinatorially defined polytopes Qn , such as the Traveling Salesman Polytope T SPn , to construct a simpler polytope Pn whose projection approximates Qn , by now is a well-established technique of “lift and project” in combinatorial optimization, see, for example, [Ba01]. In particular, a remarkable success was achieved in showing that certain exponentially large (in n) families of facets of certain series of polytopes Qn can be obtained as projections of only polynomial in n families of facets of Pn , see [LS91]. However, not much is known about how well the projections approximate metrically, even though various techniques were compared combinatorially, see [La03]. We also note that the authors of [BN01], while constructing their remarkable approximation of the Euclidean ball by the projection of a polytope with a small number of facets (cf. Section 4.4), were motivated by very practical questions. Namely, they used their approximation to reduce convex quadratic programming problems to linear programming problems (see [BN01] for details) and hence use the linear programming solver available to them to solve quadratic programs. Some basic questions regarding approximations by projections remain unanswered. 16 (4.7.1) Obstructions to being a projection. Let Q ⊂ V be a polytope. How can one possibly prove that Q cannot be the projection of a polytope P with at most N facets? In the case when Q is symmetric and P is required to be symmetric, a possible argument goes via the type 2 constant, see Theorem 4.3. Another example is the proof of [Ya91] that T SPn cannot be a projection of a polytope Pn with a polynomial in n number of facets provided the projection respects the symmetries of T SPn . In general, if the lifting P is not required to be symmetric, no viable argument seems to be known. It would be interesting to find out whether some appropriate notion of a non-symmetric type can be of help. (4.7.2) The quality of approximation of a general body. How well can a general d-dimensional convex body B be approximated by the projection of a polytope with at most N facets? In particular, the following question seems to be of interest. Suppose that B is symmetric and that the projection of a polytope P approximates B within a factor of 2. Is it true that in the worst case the number N of facets of P should be at least exponential in d, N ≥ cd for some absolute constant c > 1? In Section 5 we discuss a certain construction which suggeststhat maybe the √  d ∗ , where, as exponential bound can be broken and that we can have N = O c usual, ∗ stands for some logarithmic factors. (4.7.3) Approximation of the lp ball. Let p ≥ 1 and let n B(d, p) = (ξ1 , . . . , ξd ) : d X o ξip ≤ 1 i=1 be the unit ball in the lp norm. One can observe that the first step of the construction of Section 4.4 can be extended to B(d, p) thus providing an approximation of B(d, p) within a factor of (1 + ) by the projection of a polytope with at most
−1 N = O d facets. It is not clear whether for a general p one can replace −1 by ln −1 , though this is definitely the case for p = 1, 2, and +∞. 5. A “soft” approximation of a symmetric convex body Let B ⊂ V be a symmetric convex body. We identify V ∗ with the subspace of linear functions in the space C (B) of all continuous functions f : B −→ R. Then B ◦ can be identified with the set of linear functions f : B −→ R such that f (x) ≤ 1 for all x ∈ B. In this section, we prove the following main result. (5.1) Theorem. Let B ⊂ V be a symmetric d-dimensional convex body and let C (B) be the space of all continuous functions on B. Then there exists a polytope R ⊂ C (B) such that the following holds. (1) For all h ∈ R we have h(x) ≤ 1 for all 17 x ∈ B; (2) For any ` ∈ B ◦ there exists a function h ∈ R such that `(x) − h(x) ≤ γ`2 (x) for all x∈B and some absolute constant γ. n o √ (3) The polytope R has at most exp α d ln d vertices for some absolute constant α. If we could claim that the function h in Part (2) of the theorem is linear, then we must have had h(x) = `(x) in Part (2) and we would have obtained the representation B◦ = R ∩ V ∗ n √ o of B ◦ as the intersection of a polytope with at most exp α d ln d vertices and a subspace V ∗ . By duality,n that would o have implied that B is the projection of a √ polytope with at most exp α d ln d facets. In general, however, h is not a linear function, but, as will follow from the proof, is a piecewise polynomial. If ` ∈ B ◦
for some 0 <  < 1 then h approximates ` within an error of O 2 , so the points of B ◦ that are closer to the origin are better approximated. Intuitively, we obtain a set close to B ◦ if we slightly “bend” V ∗ and then intersect it with R. Proof of Theorem 5.1. Since B is symmetric, we can find an ellipsoid E ⊃ B centered at the origin such that 1 √ E ⊂ B ⊂ E. d On the other hand, approximating the ellipsoid by the projection of a polytope (see Section 4.4), one can construct a polytope P ⊂ W with N = O(d) facets and a linear transformation T : W −→ V such that 1 T (P ) ⊂ E ⊂ T (P ). 2 Summarizing, 1 √ T (P ) ⊂ B ⊂ T (P ). 2 d (5.1.1) Without loss of generality, we assume that P ⊂ W is full-dimensional and contains the origin in its interior. Suppose that n P = w∈W : o gi (w) ≤ 1, i = 1, . . . , N , 18 where gi : W −→ R √ are linear functions. Let us choose the smallest positive integer k > 2 d. For a multiset I of numbers from 1 to N of cardinality at most k (counting multiplicities), we let Y gI = 1 − (1 − gi ) . i∈I Hence gI : W −→ R are polynomials, deg gI ≤ k. It is immediate that gI (w) ≤ 1 for all w ∈ P . Suppose now that ` ∈ B ◦ , so ` : B −→ R is a linear function such that `(x) ≤ 1 for all x ∈ B. In view of (5.1.1), we have `(x) ≤ k for all x ∈ T (P ). Let f : W −→ R be the lifting of ` defined by f (w) = ` (T (w)) for w ∈ W . Hence f : W −→ R is a linear function and f (w) ≤ k for all w ∈ P . Therefore, k −1 f (w) ≤ 1 for all w ∈ P and hence   −1 k f ∈ conv 0, gi : i = 1, . . . , N . Therefore, (5.1.2) F = 1 − 1 − k −1 f
k  ∈ conv 0, gI :  |I| ≤ k . Now, since B symmetric, we have |`(x)| ≤ 1 for all x ∈ B. Therefore, for all w ∈ P such that T (w) ∈ B, we have |f (w)| ≤ 1 and hence (5.1.3) |F (w) − f (w)| ≤ γf 2 (w) for all w ∈ P such that T (w) ∈ B. Now we are ready to define R ⊂ C(B). Let us fix a scalar product in W and hence the Lebesgue measure on every affine subspace of W . Let us define hI ∈ C(B) by hI (x) = the average value of gI (w) over all w ∈ P ∩ T −1 (x). Let us define R to be the convex hull of the origin and all the functions hI as I ranges over all multisets with the elements from {1, . . . , N } and of cardinality at most k, counting multiplicities. Clearly, the number of vertices of R does not exceed N k , so Part(3) follows. Since hI (x) ≤ 1 for all I and all x ∈ B, Part (1) follows as well. To prove Part (2) we choose h(x) = the average value of F (w) over all w ∈ P ∩ T −1 (x), where F is defined by (5.1.2). Clearly, h ∈ R and Part (2) follows by (5.1.3).  Let ` ∈ V ∗ be a linear function ` : B −→ R. There seems to be no efficient way to check whether there is a function h ∈ R such that |`(x) − h(x)| ≤ γ`2 (x) for all x ∈ B. We can relax the condition by replacing the uniform distance by the distance in the L2 (B, µ) norm for some Borel probability measure µ on B: Z 1/2 2 kf k2 = f dµ . B 19 Then, checking whether for a given ` ∈ V ∗ there is an h ∈ R such that k` − hk2 ≤ γk`2 k2 becomes problemoof convex quadratic programming which can be solved roughly n a√
in exp O d ln d time (in the bit model). Let us choose a sufficiently small  > 0. Let us “accept” a given linear function ` ∈ V ∗ if there exists an h ∈ R such that k` − hk2 ≤ γk`k2 n √
o and “reject” it otherwise. Hence we get an algorithm of exp O d ln d complexity such that given a linear function ` : B −→ R (i) the algorithm accepts ` if `(x) ≤  for all x ∈ B; (ii) if the algorithm accepts ` then there is a function h : B −→ R with h(x) ≤ 1 for all x ∈ B and k` − hk2 ≤ γk`k2 , where γ is an absolute constant. This is somewhat similar to the situation of the “property testing” in computer science, see, for example, [Go99]. One can observe that the estimates of Theorem 5.1 can be extended in a number of ways. If we know that B can be approximated by an ellipsoid within a factor ρ ≥ 1 then we can construct a polytope R with the number of vertices not exceeding exp {αρ ln d}. More generally, we can require that R has not more than exp {αk ln d} vertices for k ≤ ρ if we replace the condition (2) in Theorem 5.1 by |kρ−1 `(x) − h(x)| ≤ γk 2 ρ−2 `2 (x). 6. Approximations by a section of the cone of positive semidefinite quadratic forms Let W be a finite-dimensional real vector space and let S(W ) be the space of all quadratic forms q : W −→ R. Let S+ (W ) ⊂ S(W ) be the convex cone of positive semidefinite quadratic forms, that is, the quadratic forms such that q(w) ≥ 0 for all w ∈ W . The membership problem for the cone S+ (W ) can be solved in time polynomial in dim W both in the algebraic and the bit models of computation. Roughly, checking that q is positive semidefinite can be done by a certain variation of the Sylvester criterion. Identifying W = Rd , we conclude that q is positive semidefinite if and only if the form
q (x) = q(x) +  ξ12 + . . . + ξd2 is strictly positive definite for all  > 0. Sylvester’s criterion then implies that the the d principle minors of q should be positive for all  > 0, which, in turn, reduces to checking that d univariate polynomials in  are positive for all  > 0. Let B ⊂ V be a d-dimensional convex body. We may try to approximate B by a set X which is the intersection of the cone S+ (W ) for some W and a d-dimensional affine subspace identified with V . The main accomplishments of this approach are associated with approximations of the cut polytope, see [DL97]. 20 (6.1) Approximating the cut polytope. For n-vectors x = (ξ1 , . . . , ξn ) and y = (η1 , . . . , ηn ), let us define the n × n matrix x ⊗ y as the matrix with the (i, j)th entry equal to ξi ηj and let Matn be the vector space of n × n matrices. Let us identify the space S (Rn ) of quadratic forms on Rn with the space of n × n symmetric matrices. The cut polytope CU Tn ⊂ S (Rn ) is defined as the convex hull of all n × n matrices x ⊗ x for all vectors x = (ξ1 , . . . , ξn ) with ξi = ±1. As is the case with the Traveling Salesman Polytope, the membership problem for the cut polytope is NP-complete, cf. [DL97]. We consider CU Tn as a subset of the space S (Rn ) of symmetric n × n matrices. Let A ⊂ S (Rn ) be the affine subspace consisting of the matrices with 1’s on the diagonal. It turns out that the intersection S+ (Rn )∩A approximates CU Tn within a logarithmic factor with respect to the center at the identity matrix I ∈ S (Rn ): CU Tn ⊂ A ∩ S+ (Rn ) ⊂ c ln n (CU Tn ) for some absolute constant c > 0. The logarithmic factor cannot be improved, see [A+06]. A variation of CU Tn is what we call the asymmetric cut polytope ACU Tn defined as the convex hull of all matrices x ⊗ y where x and y are n-vectors with the coordinates ξi , ηj = ±1. Again, the membership problem for ACU Tn is NP-complete. It turns out that ACU Tn can be tightly approximated by the projection of a section
of a cone of positive semidefinite quadratic forms. Namely, let A ⊂ S R2n be the affine
subspace of symmetric 2n × 2n matrices with 1’s on the diagonal. Let φ : S R2n −→ Matn be the projection  φ B X X C  =X and let Qn = φ A ∩ S R2n

. In words: Qn is the set of all possible n × n upper right corner submatrices of a 2n × 2n positive semidefinite matrix with 1’s on the diagonal. It is not hard to see that ACU Tn ⊂ Qn . Indeed, the matrix z ⊗ z, where z = (ξ1 , . . . , ξn , η1 , . . . , ηn ) with ξi , ηj = ±1 is positive semidefinite with 1’s on the diagonal and has the matrix x ⊗ y for x = (ξ1 , . . . , ξn ) and y = (η1 , . . . , ηn ) as its upper right corner submatrix. It turns out that Qn approximates ACU Tn within a constant factor: Qn ⊂ ACU Tn ⊂ κQn for some absolute constant κ, called the Grothendieck constant. Its exact value is not known, but it is known that 1.5708 ≈ π π √
≈ 1.7822, ≤κ≤ 2 2 ln 1 + 2 21 see [A+06] and [AN06] for survey and recent developments. We note that the membership problem for the projection of a section of a cone of positive semidefinite quadratic forms is an instance of semidefinite programming, which can be solved in polynomial time (in the bit model), though only approximately, cf. [Kl02]. Now we describe a construction for approximating a general convex body by a section of the cone of positive semidefinite forms. Let B ⊂ V be a convex body containing the origin in its interior. As in Section ◦ 2, we think of B as the polar B = (B ◦ ) to its own polar B ◦ ⊂ V ∗ . Hence n o B = x ∈ V : `(x) ≤ 1 for all ` ∈ B ◦ . Let us choose a positive integer k and let Wk be the space of all polynomials p : V ∗ −→ R, deg p ≤ k. In particular, for any fixed k, the dimension of Wk is bounded by a polynomial in the dimension of V . Let us choose a Borel probability measure µ on B ◦ . For a point v ∈ V , let qv : Wk −→ R be the quadratic form defined by Z
qv (p) = 1 − `(v) p2 (`) dµ(`) for p ∈ Wk . B◦ Clearly, if v ∈ B then the form qv is positive definite and the set n o qv : v ∈ V ⊂ S (Wk ) is an affine subspace. This allows us to define an approximation Xk to B by n o Xk = v ∈ V : qv ∈ S+ (Wk ) . Thus B ⊂ Xk for all k. To show that Xk approximates B reasonably well, we have to show that for any point v ∈ / B which is sufficiently far away from B we can find a ∗ polynomial p : V −→ R which takes large values on ` ∈ B ◦ such that `(v) > 1 and  small values everywhere else on B ◦ . Besides, the value of µ ` ∈ B ◦ : `(v) > 1 should be sufficiently large, in particular, the exterior angle measure µB ◦ discussed in Section 2.4 can be of help. In the case of the Traveling Salesman Polytope, the second author obtained the following result. (6.2) Theorem. Let us choose an  > 0 and let Vn be the ambient space of T SPn . Let T SPn◦ ⊂ Vn∗ be the polar of the Traveling Salesman Polytope with respect to its center as the origin. Then, there exists a set Qn ⊂ Vn∗ isometric to the section of the cone of positive semidefinite quadratic forms in nO(1/) variables by an affine subspace such that Qn ⊂ T SPn◦ ⊂ (n)Qn . The proof is presented in [Ve06]. It is not clear whether the bound is sharp. For example, the vertices of T SPn◦ corresponding to the standard facets xij = 0 of the T SP actually belong to Qn while the vertices of T SPn◦ corresponding to√the subtour elimination facets, see Chapter 58 of [Sc03], lie in αn Qn for αn = O ( n). 22 References [A+06] N. Alon, K. Makarychev, Yu. Makarychev, and A. Naor, Quadratic forms on graphs, Invent. Math. 163 (2006), 499–522. N. Alon and A. Naor, Approximating the cut-norm via Grothendieck’s inequality, SIAM J. Comput. 35 (2006), 787–803. [Ba01] E. Balas, Projection and lifting in combinatorial optimization, Computational combinatorial optimization (Schloß Dagstuhl, 2000), Lecture Notes in Comput. Sci., vol. 2241, Springer, Berlin, 2001, pp. 26–56. [Ba97] K. Ball, An elementary introduction to modern convex geometry, Math. Sci. Res. Inst. Publ., Flavors of Geometry, vol. 31, Cambridge Univ. Press, Cambridge, 1997, pp. 1–58. [Ba03] A. Barvinok, Approximating a norm by a polynomial, Geometric Aspects of Functional Analysis, Lecture Notes in Math., vol. 1807, Springer, Berlin, 2003, pp. 20–26. [BB05] A. Barvinok and G. Blekherman, Convex geometry of orbits, Combinatorial and Computational Geometry, Math. Sci. Res. Inst. Publ., vol. 52, Cambridge Univ. Press, Cambridge, 2005, pp. 51–77. [BN01] A. Ben-Tal and A. Nemirovski, On polyhedral approximations of the second-order cone, Math. Oper. Res. 26 (2001), 193–205. [B+89] J. Bourgain, J. Lindenstrauss, and V. Milman, Approximation of zonoids by zonotopes, Acta Math. 162 (1989), 73–141. [DL97] M. Deza and M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics, vol. 15, Springer-Verlag, Berlin, 1997. [Go99] O. Goldreich, Combinatorial property testing (a survey), Randomization methods in algorithm design (Princeton, NJ, 1997), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 43, Amer. Math. Soc., Providence, RI, 1999, pp. 45–59. [G+93] M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Second edition, Algorithms and Combinatorics, vol. 2, Springer-Verlag, Berlin, 1993. [Kl02] E. de Klerk, Aspects of Semidefinite Programming. Interior Point Algorithms and Selected Applications, Applied Optimization, vol. 65, Kluwer Academic Publishers, Dordrecht, 2002. [La03] M. Laurent, A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming, Math. Oper. Res. 28 (2003), 470–496. [LS91] L. Lovász and A. Schrijver, Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim. 1 (1991), 166–190. [Pi89] G. Pisier, The Volume of Convex Bodies and Banach Space Geometry, Cambridge Tracts in Mathematics, vol. 94, Cambridge University Press, Cambridge, 1989. [Sc03] A. Schrijver, Combinatorial Optimization. Polyhedra and Efficiency. Vols. A, B, and C, Algorithms and Combinatorics, 24, Springer-Verlag, Berlin, 2003. [Sz06] S.J. Szarek, Convexity, complexity, and high dimensions, Proceedings of the International Congress of Mathematicians, Madrid, August 22-30, 2006, Vol. II, European Mathematical Society, Zürich, Switzerland, 2006, pp. 1599–1622. [AN06] 23 [To89] [Ve06] [Ya91] N. Tomczak-Jaegermann, Banach-Mazur Distances and Finite-Dimensional Operator Ideals, Pitman Monographs and Surveys in Pure and Applied Mathematics, vol. 38, John Wiley & Sons, Inc., New York, 1989. E. Veomett, A positive semidefinite approximation of the symmetric Traveling Salesman Polytope, preprint arXiv math.CO/0610193 (2006). M. Yannakakis, Expressing combinatorial optimization problems by linear programs, J. Comput. System Sci. 43 (1991), 441–466. 24