Loading...
Please wait, while we are loading the content...
Similar Documents
On the parsimonious property of relaxations of the Symmetric Traveling Salesman Polytope
| Content Provider | Semantic Scholar |
|---|---|
| Author | Theis, Dirk Oliver |
| Copyright Year | 2007 |
| Abstract | We relate the parsimonious property of relaxations of the Symmetric Traveling Salesman Polytope to a connectivity property of the ridge graph of the Graphical Traveling Salesman Polyhedron. This relationship is quite surprising. The proof is elegant and geometric: it makes use of recent results on “flattening” parts of the boundary complex of the polar of the Graphical Traveling Salesman Polyhedron. The Symmetric Traveling Salesman Polytope STSP(n) is the convex hull of all cycles (connected 2-regular graphs) on a fixed vertex set V of cardinality n. The Graphical Traveling Salesman Polyhedron GTSP(n) is the convex hull of all connected Eulerian multi-graphs a fixed vertex set on V . It contains STSP(n) as a face, defined by a certain system of linear equations. A relaxation is a system of linear inequalities which are facet-defining for STSP(n) and GTSP(n). It has the parsimonious property if, for a certain set of linear objective functions, the following holds: the minimum of this function over the relaxation does not increase when the above mentioned equations are added to the relaxation. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://arxiv.org/pdf/0712.1269v1.pdf |
| Alternate Webpage(s) | http://arxiv.org/pdf/0712.1269.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
