The asymmetric assignment problem and some new facets of the traveling salesman polytope on a directed graph

摘要: An assignment (spanning union of node-disjoint dicycles) in a directed graph is called asymmetric if it contains at most one arc each pair $(i, j)$, $( j,i)$. The polytope the convex hull incidence vectors all assignments. A class facets described for this defined on complete digraph, associated with certain odd-length closed alternating trails. inequalities defining these are also facet inducing traveling salesman same digraph. Furthermore, distinct from classes identified earlier.