A Positive Semidefinite Approximation of the Symmetric Traveling Salesman Polytope

Details A Positive Semidefinite Approximation of the Symmetric Traveling Salesman Polytope A Positive Semidefinite Approximation of the Symmetric Traveling Salesman Polytope

2006-10-05

arxiv.org/abs/math/0610193v1

Mathematics

Combinatorics

25 pages

Scientific paper

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 subspace. We show that P_k is contained in B for each k. When B is the Symmetric Traveling Salesman Polytope on n cities T_n, we show that the scaling of P_k by n/k+ O(1/n) contains T_n for k no more than n/2. Membership for P_k is computable in time polynomial in n (of degree linear in k). We discuss facets of T_n that lie on the boundary of P_k. We introduce a new measure on each facet defining inequality for T_n in terms of the eigenvalues of a quadratic form. Using these eigenvalues of facets, we show that the scaling of P_1 by n^(1/2) has all of the facets of T_n defined by the subtour elimination constraints either in its interior or lying on its boundary.

Affiliated with

Also associated with

No associations

Rating

A Positive Semidefinite Approximation of the Symmetric Traveling Salesman Polytope does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Positive Semidefinite Approximation of the Symmetric Traveling Salesman Polytope, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Positive Semidefinite Approximation of the Symmetric Traveling Salesman Polytope will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-656556