ISSN:
1439-6912
Keywords:
Primary: 52 B 05
;
52 B 12
;
Secondary: 90 C 27
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract We study the facial structure of two important permutation polytopes in $$\mathbb{R}^{n^2 } $$ , theBirkhoff orassignment polytopeB n , defined as the convex hull of alln×n permutation matrices, and theasymmetric traveling salesman polytopeT n , defined as the convex hull of thosen×n permutation matrices corresponding ton-cycles. Using an isomorphism between the face lattice ofB n and the lattice of elementary bipartite graphs, we show, for example, that every pair of vertices ofB n is contained in a cubical face, showing faces ofB n to be fairly special 0–1 polytopes. On the other hand, we show thatevery 0–1d-polytope is affinely equivalent to a face ofT n , ford∼logn, by showing that every 0–1d-polytope is affinely equivalent to the asymmetric traveling salesman polytope of some directed graph withn nodes. The latter class of polytopes is shown to have maximum diameter [n/3].
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01844844
Permalink
