Grötschel–Padberg diameter conjecture for the symmetric traveling salesperson polytope
Statement
Let be the set of Hamiltonian cycles on vertices, and let
be the symmetric traveling salesperson polytope, where denotes the characteristic vector of the Hamiltonian cycle . Its skeleton is the graph whose vertices are the vertices of and whose edges are its one-dimensional faces. Write for the maximum edge distance between any pair of vertices of a graph .
Grötschel–Padberg conjecture. For every integer , the diameter of the skeleton of the symmetric traveling salesperson polytope is
This conjecture is motivated by the study of edge-following algorithms for linear programming and by the relationship between polytope diameter and the Hirsch conjecture. It is based on complete descriptions for and remains open.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.