A Positive Semidefinite Approximation of the Symmetric Traveling Salesman Polytope
| dc.creator | Veomett, Ellen | |
| dc.date | 2006-10-05 | |
| dc.date.accessioned | 2026-07-07T07:28:46Z | |
| dc.date.available | 2026-07-07T07:28:46Z | |
| dc.description | 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. | |
| dc.description | 25 pages | |
| dc.identifier | https://arxiv.org/abs/math/0610193 | |
| dc.identifier | http://arxiv.org/abs/math/0610193 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/117853 | |
| dc.subject | Combinatorics | |
| dc.subject | Metric Geometry | |
| dc.subject | 52A20; 52A27; 52A21; 52B55; 68W25; 68Q25 | |
| dc.title | A Positive Semidefinite Approximation of the Symmetric Traveling Salesman Polytope | |
| dc.type | text |