Showing math.COShow all
2 papers · 1 filter
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.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…