All 0-1 polytopes are traveling salesman polytopes

DOI10.1007/BF01844844zbMath0859.52002OpenAlexW1989428327MaRDI QIDQ1924487

A. Sarangarajan, Billera, Louis J.

Publication date: 20 October 1996

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01844844

zbMATH Keywords

permutation polytopesassignment polytopeasymmetric traveling salesman polytope0--1 polytope

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27)

Related Items (14)

Facets of the balanced minimal evolution polytope ⋮ Partial Permutation and Alternating Sign Matrix Polytopes ⋮ Any finite group is the group of some binary, convex polytope ⋮ A lexicographic semiorder polytope and probabilistic representations of choice ⋮ Semidefinite approximations of conical hulls of measured sets ⋮ An analog of the Cook theorem for polytopes ⋮ What is known about unit cubes ⋮ \(k\)-neighborly faces of the Boolean quadric polytopes ⋮ The common face of some 0/1-polytopes with NP-complete nonadjacency relation ⋮ How to recycle your facets ⋮ Equivalence classes of full-dimensional 0/1-polytopes with many vertices ⋮ Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program ⋮ On the facial structure of symmetric and graphical traveling salesman polyhedra ⋮ A combinatorial study of partial order polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Convex polyhedra of doubly stochastic matrices III. Affine and combinatorial properties of \(\Omega\)
• Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
• Lectures on Polytopes

This page was built for publication: All 0-1 polytopes are traveling salesman polytopes