All 0–1 polytopes are traveling salesman polytopes | Zendy

Louis J. Billera | Zendy; A. Sarangarajan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

All 0–1 polytopes are traveling salesman polytopes

Author(s) -

Louis J. Billera,

A. Sarangarajan

Publication year - 1996

Publication title -

combinatorica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.106

H-Index - 58

eISSN - 1439-6912

pISSN - 0209-9683

DOI - 10.1007/bf01844844

Subject(s) - combinatorics , polytope , mathematics , convex hull , travelling salesman problem , bipartite graph , regular polygon , vertex (graph theory) , polyhedral combinatorics , lattice (music) , permutation (music) , graph , discrete mathematics , convex set , geometry , algorithm , convex optimization , physics , acoustics

We study the facial structure of two important permutation polytopesin Rn2, the Birkhoff or assignment polytope B n , defined as theconvex hull of all n \Theta n permutation matrices, and the asymmetrictraveling salesman polytope T n , defined as the convex hull of thosen \Theta n permutation matrices corresponding to n-cycles. Using an isomorphismbetween the face lattice of B n and the lattice of elementarybipartite graphs, we show, for example, that every pair of vertices ofB n ...

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research