On the facial structure of Symmetric and Graphical Traveling Salesman Polyhedra

Simple item page
dc.creatorTheis, Dirk Oliver
dc.date2007-12-08
dc.date2009-04-10
dc.date.accessioned2026-07-07T13:01:49Z
dc.date.available2026-07-07T13:01:49Z
dc.descriptionThe Symmetric Traveling Salesman Polytope $S_n$ for a fixed number $n$ of cities is a face of the corresponding Graphical Traveling Salesman Polyhedron $P_n$. This has been used to study facets of $S_n$ using $P_n$ as a tool. In this paper, we study the operation of "rotating" (or "lifting") valid inequalities for $S_n$ to obtain a valid inequalities for $P_n$. As an application, we describe a surprising relationship between (a) the parsimonious property of relaxations of the Symmetric Traveling Salesman Polytope and (b) a connectivity property of the ridge graph of the Graphical Traveling Salesman Polyhedron.
dc.identifierhttps://arxiv.org/abs/0712.1269
dc.identifierhttp://arxiv.org/abs/0712.1269
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/226274
dc.subjectCombinatorics
dc.subjectOptimization and Control
dc.subject52B12, 90C05, 90C35
dc.titleOn the facial structure of Symmetric and Graphical Traveling Salesman Polyhedra
dc.typetext

Files

Collections

arXiv