On the facial structure of Symmetric and Graphical Traveling Salesman Polyhedra

Details On the facial structure of Symmetric and Graphical Traveling Salesman Polyhedra On the facial structure of Symmetric and Graphical Traveling Salesman Polyhedra

2007-12-08

arxiv.org/abs/0712.1269v2

Mathematics

Combinatorics

Scientific paper

The 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.

Affiliated with

Also associated with

No associations

Rating

On the facial structure of Symmetric and Graphical Traveling Salesman Polyhedra 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 On the facial structure of Symmetric and Graphical Traveling Salesman Polyhedra, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the facial structure of Symmetric and Graphical Traveling Salesman Polyhedra will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-325053