On the facial structure of Symmetric and Graphical Traveling Salesman Polyhedra

2007/12/08 by Dirk Oliver Theis, Theis, Dirk Oliver
Computer Science · Engineering · Mathematics · #52B12 #90C05 #90C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #math.CO #math.OC #msc:52B12 #msc:90C05 #msc:90C35

paper · pdf · doi:10.48550/arxiv.0712.1269

openalex publication_date 2007/12/08 · arxiv created 2009/04/10 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• On some lower bounds on the number of bicliques needed to cover a bipartite graph

Related

• An Efficient Approximation of the Traveling Salesman Polytope Using Lifting Methods
• A note on the relationship between the Graphical Traveling Salesman Polyhedron, the Symmetric Traveling Salesman Polytope, and the Metric Cone
• A Positive Semidefinite Approximation of the Symmetric Traveling Salesman Polytope
• The Circlet Inequalities: A New, Circulant-Based Facet-Defining Inequality for the TSP
• The Graph of the Pedigree Polytope is Asymptotically Almost Complete\n (Extended Abstract)