3 papers
math.CO2006
An Efficient Approximation of the Traveling Salesman Polytope Using Lifting Methods
Ellen Veomett
For the Traveling Salesman Polytope on n cities T_n, we construct its approximation Q_k, k=1, 2, . . ., n^(1/3) using a projection of a polytope whose number of facets is polynomia…
math.MG2006
The computational complexity of convex bodies
Alexander Barvinok, Ellen Veomett
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 in V, does x belong…
math.CO2006
A Positive Semidefinite Approximation of the Symmetric Traveling Salesman Polytope
Ellen Veomett
For a convex body B in a vector space V, we construct its approximation P_k, k=1, 2, . . . using an intersection of a cone of positive semidefinite quadratic forms with an affine s…