All 0-1 polytopes are traveling salesman polytopes
Two permutation polytopes are studied: the assignment polytope \(B_n\), defined as the convex hull of the set of \(n\times n\) permutation matrices, and the asymmetric traveling salesman polytope (TSP) \(T_n\), defined as the convex hull of the set of those \(n\times n\) permutation matrices corresponding to \(n\)-cycles. It is proved that the face lattice of \(B_n\) is isomorphic to the lattice of all elementary subgraphs of \(K_{n,n}\), the complete bipartite graph with colour classes of size \(n\) (the elementary subgraphs are those having the property that each of its edges is in some matching), and that all faces of \(B_n\) have the property that any two vertices are contained in a cubical subface of dimension at most the integer part of \(n/2\). Concerning the TSP, the authors prove that any 0-1 polytope \(P \subset R^d\) with \(2^d-k\) vertices, \(k>1\), appears as a face of \(T_n\) for \(n\geq (4k+1)d\) and is the asymmetric TSP of some directed graph with \(n\) nodes (the asymmetric TSP \(T_D\) of the directed graph \(D\) is the convex hull of the set of permutation matrices associated to the tours in \(D)\). The maximum diameter of \(T_D\) over all directed graphs on \(n\) nodes is proved to be the integer part of \(n/3\).
- scientific article; zbMATH DE number 848091
- The monotonic diameter of traveling salesman polytopes
- The Asymmetric Assignment Problem and Some New Facets of the Traveling Salesman Polytope on a Directed Graph
- A Bound of 4 for the Diameter of the Symmetric Traveling Salesman Polytope
- scientific article; zbMATH DE number 3943559
- Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
- Convex polyhedra of doubly stochastic matrices III. Affine and combinatorial properties of
- scientific article; zbMATH DE number 124861 (Why is no real title available?)
- scientific article; zbMATH DE number 848091 (Why is no real title available?)
- Lectures on Polytopes
- The k-assignment polytope
- Any finite group is the group of some binary, convex polytope
- An analog of the Cook theorem for polytopes
- On the mean radius of permutation polytopes
- A combinatorial study of partial order polytopes
- \(k\)-neighborly faces of the Boolean quadric polytopes
- The common face of some 0/1-polytopes with NP-complete nonadjacency relation
- On the facial structure of symmetric and graphical traveling salesman polyhedra
- How to recycle your facets
- Equivalence classes of full-dimensional 0/1-polytopes with many vertices
- Facets of the balanced minimal evolution polytope
- scientific article; zbMATH DE number 3849282 (Why is no real title available?)
- A Bound of 4 for the Diameter of the Symmetric Traveling Salesman Polytope
- A lexicographic semiorder polytope and probabilistic representations of choice
- What is known about unit cubes
- scientific article; zbMATH DE number 848091 (Why is no real title available?)
- Partial permutation and alternating sign matrix polytopes
- Semidefinite approximations of conical hulls of measured sets
- Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
- Traveling salesman polytopes and cut polytopes. Affine reducibility
- c-Birkhoff polytopes
- Near-derangements and their polytopes
This page was built for publication: All 0-1 polytopes are traveling salesman polytopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1924487)
